Szacowanie czasu sortowania dla n elementów.

Question

Witam,

Zrobiłem program sortujący n elementową tablicę, ale dla n > 50000 chciałbym wyświetlić szacowany czas wykonania operacji. Ma ktoś jakiś pomysł ? :)

Dzięki :P

Answer 1

1. Pokaż kod
2. Podaj czasy dla n = 1000,2000,3000,10000,20000,30000

Comments

Zroibłem funkcję, która przyjmuje liczbę n a następnie wypisuje szacowany czas.

Nie chciałbym rozpatrywać przedziałami if(n > 10000 && n < 40000) czas = 20;

---

Powiedzmy, że czas wykonania programu to około (n*n*p + c), gdzie p oraz c są zależne od sprzętu. Dla różnych algorytmów to wyrażenie wygląda różnie, ale to powinno jakoś się zgadzać przy bubblesort.
Przykładowo (dane wymyślone, samo wyrażenie na czas też musisz dostosować):
Dla n=10000 czas wykonania = 20s
Dla n=20000 czas wykonania = 78s
10000*10000*p + c = 20s
20000*20000*p + c = 78s
p*(400000000-100000000) = 78s-20s = 58s
300000000*p = 58s
p = 19.3s / 10^8
c = 0.7s
Wszystko "dowiedziane", mamy wzór:
t = n*n*19.3s/10^8 + 0.7s
Powinieneś mierzyć czas w warunkach podobnych do tych, w których później program będzie uruchamiany.

---

Serdeczne dzięki kolego  :)