Złożoność algorytmu

2011-10-14T12:44:40+02:00

Jaka jest najmniejsza wartość n, dla której algorytm o złożoności 100 *n^{2 działa ( na tej samej maszynie) szybciej od algorytmu o złożoności 2}n

2011-10-14T12:46:01+02:00

Wystarczy (dla każdego pytania tego typu) rozwiązać równanie

$100(n<sup>2) < 2</sup>n$
(100(n^{2) < 2}n)

2011-10-14T12:51:20+02:00

jeśli działa szybciej nie powinno być na odwrót 100*(n^{2) > 2}n, wtedy dla n=1 zależność ta zostaje spełniona

2011-10-14T12:55:18+02:00

DBest napisał(a)

jeśli działa szybciej nie powinno być na odwrót 100*(n^{2) > 2}n, wtedy dla n=1 zależność ta zostaje spełniona

Pomyśl logicznie. Złożoność. Im większa tym działa szybciej? Chyba nie do końca. Więc imho warunek w drugą stronę jak napisał MSM.

Jeśli się nie walnąłem w obliczeniach to n>=15 spełnia ten warunek.

2011-10-14T12:59:27+02:00

zgadza się, stare przyzwyczajenia wzięły swoje.
Dla n=15 warunek zostaje spełniony dzięki

2011-10-16T19:23:03+02:00

a jak obliczyć złożoność obliczeniową pseudokodu sortowania bąbelkowego dostępnego na wikipedii?

Liczba odpowiedzi na stronę

Zarejestruj się i dołącz do największej społeczności programistów w Polsce.

Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.