0 Daumen
1,1k Aufrufe

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(n2) < O(n3) < O(2n).

(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} \), 5n, n·log(n), n1-∈ , \( \frac{n}{loglog(n)} \), n4/3 ·log(n), (4/3)n , n·2 ^ \( \sqrt{log(n)} \)

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

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

Mir ist jedoch nicht so ganz klar wieso n1-∈ < \( \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!

Avatar von
wieso n1-∈ < \( \frac{n}{loglog(n)} \) gilt?

Was bedeutet das "∈" in n1-∈?

1 Antwort

0 Daumen
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)\).

Avatar von 106 k 🚀

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community