Rozwiązuję pytanie dotyczące algorytmu i moja analiza polega na tym, że będzie on działał na O (2 ^ sqrt (n)). Jak duże to jest? Czy to odpowiada O (2 ^ n)? Czy nadal jest to czas niepomiarowy?
big-o
algorithm-analysis
Gaara
źródło
źródło
Odpowiedzi:
To interesujące pytanie. Na szczęście, gdy już wiesz, jak to rozwiązać, nie jest to szczególnie trudne.
Dla funkcji f : N → R + i g : N → R + mamy f ∈ O ( g ) tylko wtedy, gdy lim sup n → ∞ f ( n ) / g ( n ) ∈ R .
Funkcja f : N → R + ma co najwyżej wzrost wielomianowy wtedy i tylko wtedy, gdy istnieje stała k ∈ N taka, że f ∈ O ( n ↦ n k ). Praca Zróbmy to się arbitralne, ale stałej k ∈ N .
lim sup n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ 2 ( n 1/2 ) / n k =
lim n → ∞ e log (2) n 1/2 / e log ( n ) k =
lim n → ∞ e log (2) n 1/2 - log ( n ) k = ∞ ∉ R
Pierwsza równość jest prawdziwa, ponieważ zarówno nominator, jak i mianownik są monotonicznie rosnącymi stałymi funkcjami. Druga równość wykorzystuje tożsamość x y = e log ( x ) y . Limit nie jest skończony, ponieważ wykładnik w wyrażeniu końcowym nie jest ograniczony powyżej. Bez formalnego dowodu można założyć, że wiadomo, że n 1/2 dominuje log ( n ) asymptotycznie. Dlatego omawiana funkcja przekracza wzrost wielomianowy.
Jednak jego wzrost jest ściśle mniejszy niż wykładniczy, gdzie wykładniczy jest zdefiniowany (w tym celu przeze mnie) jako O ( n ↦ 2 c n ) dla c > 0. Wykazanie tego jest jeszcze bardziej proste.
lim sup n → ∞ 2 c n / 2 ( n 1/2 ) = lim n → ∞ 2 c n - n 1/2 = ∞ ∉ R
dla dowolnego ustalonego c > 0. Dlatego złożoność funkcji jest gdzieś naprawdę pomiędzy wielomianem a wykładnikiem.
źródło
Jak duże to jest? Cóż, O (2 ^ sqrt (n)) jest dokładnie jak duży jest :-(
Aby dowiedzieć się, co to znaczy, wyobraź sobie, że twój algorytm nie byłby tylko O (2 ^ sqrt (n)), ale że faktycznie zajmuje dokładnie 2 ^ sqrt (n) nanosekund na twoim komputerze:
n = 100: 2 ^ 10 = 1024 nanosekund. Kompletny brak czasu. n = 1000: 2 ^ 31,xxx = 2 miliardy nanosekund. Dwie sekundy, to zauważalne. n = 10 000: 2 ^ 100 ≈ 10 ^ 30 nanosekund = 10 ^ 21 sekund = 30 bilionów lat.
Jest to o wiele lepsze niż 2 ^ n nanosekundy, gdzie n = 100 zajęłoby 30 trylionów lat, ale wciąż rozmiar problemów, które można rozwiązać, jest dość ograniczony. Jeśli uważasz, że problem można rozwiązać, jeśli komputer może go rozwiązać w ciągu jednego tygodnia, to około 6 x 10 ^ 14 nanosekund, czyli około n = 2400. Z drugiej strony, do n = 400 można rozwiązać w ciągu milisekundy.
(W praktyce dla n = 10 000 zarówno O (2 ^ sqrt (n)), jak i O (2 ^ n) zajmują dokładnie ten sam czas: zbyt długo, aby na nie poczekać.)
Przekracza dowolny wielomian. Weź inny algorytm zajmujący n ^ 1000 sekund. Co jest praktycznie nierozwiązywalne dla n = 2. Ten algorytm trwa dłużej, zanim n wyniesie około 885 milionów. Ale tak naprawdę, kogo to obchodzi? W tym momencie liczba lat, które zajmują oba algorytmy, wynosi 9 000 cyfr.
źródło