Złożoność czasowa w porządku rosnącym - wydajność, złożoność czasowa, kompilacja środowiska wykonawczego

Jaka jest rosnąca kolejność wzrostu następujących funkcji:

1. 2 ^ ((logn) ^ 1/2)

2. 2 ^ n

3. 2 ^ (n / 2)
4. n ^ (4/3)
5. n (logn) ^ 3
6. n ^ logn
7. 2 ^ (n ^ 2)

8. n!

   log n jest z bazą 2.

Odpowiedzi:

• Możemy natychmiast to wydedukować n! jest najwyższym porządkiem, ponieważ jest równy

  

  ... i n^n część znacznie przekracza wszelkie inne funkcje.

• Od

  

  Możemy wywnioskować, że (1) jest mniejszy niż inne funkcje z n jako podstawa, np. (4), (5) i (6). W rzeczywistości jest to mniej niż wszystko innych funkcji.

• (3) <(2), ponieważ ten ostatni jest poprzednim kwadratem.

• (2) <(7), ponieważ ten ostatni jest pierwszym do władzy n.

• (4) <(6), od log n > 4/3.

• Od ten post, log n rośnie wolniej niż jakakolwiek pozytywna moc n. W związku z tym:

  

  Tak więc (5) <(4), (6)

• Korzystając z transformacji prawa logarytmicznego uzyskujemy:

  

  Tak więc (6) <(3).

Łącząc wszystkie powyższe kroki rozumowania, możemy wydedukować kolejność rosnącą:

(1).

(5).

(4).

(6).

(3).

(2).

(7).

(8).