Erklärung der O-Notation

Question

Hallo Leute,

kann mir einer von euch helfen und mir sagen, auf welche Eigenschaften ich bei der Bestimmung der Laufzeit achten muss. Ich bin mir nie so richtig sicher und kann es bei einigen Beispielen gar nicht bestimmen.

Zum Beispiel bei der Funktion √4²ⁿ   oder  (1+1/n)*(1+2/n).

Ich wüsste nicht wie ich hier vorgehen muss um hier die Laufzeit in der O-Notation angeben zu können.

Danke für eure Hilfe.

Answer 1

Wichtig ist hierbei ein ungefähres Verständnis der Funktionen zu haben. Ich merke mir immer folgenden Zusammenhang und versuche die aktuelle Funktion, die ich als Aufgabe zu lösen habe hier einzusetzen bzw. einzureihen:

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(N^3) < O(k^N)

Man kann diese Gliederung noch genauer und ausführlicher machen. Aber das ist zunächst meine Gedächtnisstütze :)