Złożoność czasowa 2 ^ sqrt (n)

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?

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.

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.