O-Kalkül

[system]

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

[vaiquero]

O-Kalkül
Simple Frage, woran erkenn ich ob eine Schleife konstant, O(n) oder log n hat? Und kann eine Schleife auch n^2 haben? Ich seh da kein System dahinter. Kann das jemand mal sehr simpel erklären? Wie die systematik ist?

Edit:
Wenn ich das richtig versteh dann kann eine Schleife keinen aufwand haben der größer als O(n) ist, da sonst die schleife nicht terminieren würde. was ja nicht unser Ziel, algorithmen sollen ja immer terminieren.

alles unterhalb von O(n) ist möglich, seh ich das richtig?
Im umkehrschluss würde das bedeuten, wenn es keine lineare schleife ist im klassischen sinne [for(int i =0, i < n,i++)] dann bleibt nur noch log n übrig, es sei den sie wäre konstant?
also wäre for(int i = 1, i < n, i *= 2) => O(log n)
for(int i = 1, i < n, i *= 5) => O(log n)
for(int i = 1, i > n, i /= 3) => O(log n)

was wäre den for(int i = 1, i < n, i++) {i *= 3; } wäre das auch O(log n)?

noch ein Edit:
Was wäre (1 + n * log n)/2 in O?

[iridium]

---

@vaiquero

Simple Frage, woran erkenn ich ob eine Schleife konstant, O(n) oder log n hat? Und kann eine Schleife auch n^2 haben? Ich seh da kein System dahinter. Kann das jemand mal sehr simpel erklären? Wie die systematik ist?

Du stellst eine Funktion auf, die die Anzahl der Operationen (Schleifendurchläufe * Schleifenrumpf, letzterer ggf. in Abhängigkeit von der Zählvariable) in Abhängigkeit von den Eingabewerten angibt. Dann drückst du diese Funktion unter Vernachlässigung von konstanten Faktoren im O-Kalkül aus. Pattern Matching alleine ist ein Anfang, wird dir aber nicht ausreichen.

Edit:
Wenn ich das richtig versteh dann kann eine Schleife keinen aufwand haben der größer als O(n) ist, da sonst die schleife nicht terminieren würde. was ja nicht unser Ziel, algorithmen sollen ja immer terminieren.

Welche Laufzeit (in Abhängigkeit von n) hat denn das hier?

for(int i=1; i<n*n*n; ++i) { doSomethingInO(1); }

alles unterhalb von O(n) ist möglich, seh ich das richtig?
Im umkehrschluss würde das bedeuten, wenn es keine lineare schleife ist im klassischen sinne [for(int i =0, i < n,i++)] dann bleibt nur noch log n übrig, es sei den sie wäre konstant?

nein, siehe oben

also wäre for(int i = 1, i < n, i *= 2) => O(log n)

ja

            for(int i = 1, i < n, i *= 5) => O(log n)

ja

            for(int i = 1, i > n, i /= 3) => O(log n)

nein (wie viele Durchläufe macht diese Schleife?)

was wäre den for(int i = 1, i < n, i++) {i *= 3; } wäre das auch O(log n)?

noch ein Edit:
Was wäre (1 + n * log n)/2 in O?

(1 + n * log n)/2 = 1/2 + 1/2 * n * log(n)
Konstante Terme und konstante Faktoren können im O-Kalkül vernachlässigt werden.

[system]

---

@iridium

for(int i = 1, i > n, i /= 3) => O(log n)

nein (wie viele Durchläufe macht diese Schleife?)

Ich würde sagen, diese Lösung sei fast richtig für 0 < n < 1. Für n >= 1/3 wird die Schleife 1x durchlaufen, für 1/3 > n >= 1/9 2x usw… Mit anderen Worten ist der Aufwand:

T(n) = O(log_3(1/n)) = O(log(1/n) / log(3)) = O(log(1/n)) = O(-log(n)).

Edit: OK, ich irre mich, denn i ist ganzzahlig. Bei double wäre das aber in der Tat O(-log(n)).

[vaiquero]

---

Welche Laufzeit (in Abhängigkeit von n) hat denn das hier?
for(int i=1; i<nnn; ++i) { doSomethingInO(1); }

hmm ich würde sagen O(N^3) da i von N abhängt und der t() um n^3 steigt.

[quote]
noch ein Edit:
(1 + n * log n)/2 = 1/2 + 1/2 * n * log(n)
Konstante Terme und konstante Faktoren können im O-Kalkül vernachlässigt werden.[/quote]

dann wäre der Aufwand O(n * log n)? komisch das hat nen tutor bei korrektur aber durchgestrichen als falsch.