Zeitkomplexität aufsteigend

Question

Was die aufsteigende Reihenfolge der Wachstumsrate der folgenden Funktionen ist:

1. 2^((log n)^1/2)

2. 2^n

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

8. n!

   log n ist mit der Basis 2.

Answer 1

• Wir können sofort ableiten, dass n! die höchste Ordnung ist, wie es zu

  

  gleich ... und der n^n Teil übertrifft bei weitem die anderen Funktionen.

• Da

  

  können wir ableiten, daß (1) kleiner als andere Funktionen mit n als Base, z.B. (4), (5) und (6). In der Tat ist es weniger als alle der anderen Funktionen.

• (3) < (2), da letzteres das ehemalige Quadrat ist.

• (2) < (7), da letzterer der ehemalige an die Macht n ist.

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

• Von this post wächst log n langsamer als jede positive Kraft dern. Deshalb:

  

  So (5) < (4), (6)

• Unter Verwendung eines Transformations Logarithmus Gesetz wir folgendes erhalten:

  

  So (6) < (3).

---

alle der Argumentation Schritte Kompilieren oben, schließen wir die aufsteigende Reihenfolge zu sein:

(1).

(5).

(4).

(6).

(3).

(2).

(7).

(8).