Asymptotisches Wachstum Reihenfolge?

Question

Hallo, meine Frage bezieht sich auf das Asymptotische Wachstum (Landau Notation).

Ich orientiere mich immer an dieser Reihenfolge:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ).

(Wenn jemand noch eine verbesserte Reihenfolge hat, wäre ich sehr dankbar!!)

Auf jeden Fall ist meine Aufgabe dass ich die folgenden Funktionen nach ihrem asymptotischen Wachstum einordne:

\( \frac{n}{1000} \), n^\( \frac{4}{3} \), 5ⁿ, n·log(n), n^1-∈ , \( \frac{n}{loglog(n)} \), n^4/3 ·log(n), (4/3)ⁿ , n·2 ^ \( \sqrt{log(n)} \)

Es ergibt sich die folgende Reihenfolge im Hinblick auf das asymptotische Wachstum:

n^1-∈ < \( \frac{n}{loglog(n)} \) < \( \frac{n}{1000} \) < n·log(n) < n·2^\( \sqrt{log(n)} \) < n^4/3 <  n^4/3 ·log(n) < (4/3)ⁿ < 5ⁿ .

Mir ist jedoch nicht so ganz klar wieso n^1-∈ < \( \frac{n}{loglog(n)} \) gilt?

Könnte mir das bitte jemand erklären? Und wie werden Konstanten behandelt? Fallen die einfach weg?

Danke schonmal für die Erklärungen!

Comments

wieso n^1-∈ < \( \frac{n}{loglog(n)} \) gilt?

Was bedeutet das "∈" in n^1-∈?

Answer 1

Und wie werden Konstanten behandelt? Fallen die einfach weg?

Sie fallen nicht einfach weg.

Wie sie behandelt werden, kommt auf den Zusammenhang an.

Zum Beispiel ist \(O(2n) = O(3n)\) aber \(O(n^2) \neq O(n^3)\).