Komplexitätsanalyse

[Ghost (Gast)]

Hi,

habe einige Aufgaben zur Komplexitätsanalyse und wollte wissen, ob ich 
diese richtig gelöst habe. Habe damit erst angefangen und weiß noch 
nicht so viel darüber.

1)

int sum = 0;
for(int n = N; n > 0; n /=2)
    for(int i = 0; i < n; i++)
        sum++;

Da n immer halbiert wird, geht man über die erste Schleife mit log2(N)+1 
drüber. Bei N = 8:
8/2/2/2 = 1 und dann noch mit Truncating 1/2 = 0.5, Nachkommastelle 
entfällt (wobei man sich die 1 bei großen Ns schenken kann).

In die zweite Schleife geht man dann nochmal log2(N)+1 mal drüber. Also 
wird sum (log2(N)+1)^2 mal inkrementiert (oder vereinfacht (log2(N))^2.


2)

int sum = 0;
for(int i = 1; i < N; i*= 2)
   for(int j = 0; j < i; j++)
       sum++;

Erste for-Schleife wird log2(N) mal durchlaufen.
Genauso müsste es für die zweite sein.
also wieder (log2(N))^2???

3)

int sum = 0;
for(int i = 1; i < N; i*= 2)
   for(int j = 0; j < N; j++)
       sum++;

Erste Schleife wird log2(N) mal durchlaufen.
Die zweite Schleife wird N mal durchlaufen
Also
N*log2(N)

Stimmen diese Überlegungen. Und falls nicht, was habe ich dann 
falschgemacht?

Greets

[mh (Gast)]

Warum probierst du es nicht aus? Du gibst ein N vor und schaust was bei 
sum herauskommt.
Ich würde sagen deine ersten beiden stimmen nicht.

[Yalu X. (yalu) (Moderator)]

mh schrieb:
> Ich würde sagen deine ersten beiden stimmen nicht.

Ich auch.

> was habe ich dann falschgemacht?

Das:

> In die zweite Schleife geht man dann nochmal log2(N)+1 mal drüber.

Übrigens: Statt log₂(N) scheibt man bei Komplexitätsbetrachtungen
üblicherweise log(N), da sich die Basis des Logarithmus nur in einem
konstanten Faktor widerspiegelt.

[Ghost (Gast)]

Also so wie ich das sehe, habe ich sowohl bei 1) als auch bei 2) genau 
den gleichen Fehler gemacht.
Bei 1) wird das n ja immer wieder halbiert. Also müsste es doch auch 
etwas logarithmisches sein?
Zuerst wird die innere Schleife N mal, dann N/2 mal, dann N/4 mal 
durchlaufen (also wird log N mal diese Halbierung vorgenommen, die sich 
dann aufaddieren) Ob das Ding dann noch N/8 mal durchlaufen wird, hängt 
davon ab, mit welcher 2er Potenz man N darstellen kann.

Ich sehe, dass es falsch ist, aber ich weiß nicht, was ich bei 1) und 2) 
noch korrigieren muss (habe erst gestern angefangen, mich damit 
auseinanderzusetzen). Kann mir jemand sagen, was ich ändern muss?

[Yalu X. (yalu) (Moderator)]

Ghost schrieb:
> Zuerst wird die innere Schleife N mal, dann N/2 mal, dann N/4 mal
> durchlaufen (also wird log N mal diese Halbierung vorgenommen, die sich
> dann aufaddieren)

Eben. Dann addiere doch einfach mal N + N/2 + N/4 + N/8 + ... + 1
zusammen. Damit die Rechnung nicht zu kompliziert wird, kannst du ja
zunächst davon ausgehen, dass N eine Zweierpotenz ist. Für andere Werte
von N wird das Ergebnis nicht grundlegend davon abweichen.

[Johann L. (gjlayde)]

ad 1)

Von innen nach aussen: sum hat Größenordnung n² und davon sind n 
Additionen auszuführen, eine davon kostet O(log(n²)) = O(log(n)). Die 
innere Schleife kostet also O(n·log(n)).

Eingesetzt in die äussere Schleife ist's

$$\mathcal{O} \left( \sum_{n=0}^{\log N} 2^n \log(2^n)\right) = \mathcal{O} \left( \sum_{n=0}^{\log N} n\cdot 2^n\right) \subseteq \mathcal{O} \left( N\cdot \log^2(N)\right)$$

[Ghost (Gast)]

Vielen Dank für eure Hilfe,

mit ist die ganz Funktionsweise noch schleierhaft:

Johann L. schrieb:
> davon sind n
> Additionen auszuführen, eine davon kostet O(log(n²)) = O(log(n))

Warum ist das so? Also wie komme ich darauf, dass eine 
Inkrementierungsoperation O(log(n)) kostet?


Wieso kann ich

Johann L. schrieb:
> O(log(n²)) = O(log(n))

schreiben (mathematisch geht das ja nicht). Was genau ist das mit dem 
n²? Die Größenordnung n² müsste sich ja dadurch ergeben, dass es 2 
for-Schleifen sind. Aber wie wir im weiteren Verlauf sehen, ist die 
Komplexität der for-Schleifen nicht quadratisch. Welche Bedeutung hat es 
dann, dass man zuerst n² schreibt?

Könnte jemand die aufgestellten Formeln genauer erläutern, warum dort

$$2^n$$

 auftaucht bzw. wie man darauf überhaupt kommt (v.a. dass das eine 
Teilmenge von von dem ganz rechts stehenden Term ist). Ich verstehe es 
noch nicht wie man auf den ganzen Term kommt.

[Ghost (Gast)]

Denn ich hätte jetzt gesagt:

Die innere Schleife wird log(N) mal durchlaufen, dann wäre das ja dann

log(N)* n*log(n)

Aber dann müsste man ja das kleine 'n' irgendwie durch das große 
darstellen, oder. Wenn man n durch N ersetzen würde, würde man auch auf 
einen oben genannten Term kommen, aber das dürfte Zufall sein.
Wäre dankbar, wenn mir jemand das genau erklären könnte.

[Johann L. (gjlayde)]

Die innere Schleife ist

$$\text{sum}(n) = \sum_{j=0}^{n-1} j = \frac n2(n-1)$$

es sind also Zahlen in der Größenordnung n² zu addieren, und das kostet 
O(log(n²)). Da log(n²) = 2·log(n) ist
   O(log(n²)) = O(log(n))
Ganz exakt müsste man das auch für die Laufvariable machen und für jedes 
Summanden in Abhängigkeit von der Laufvariable und das aufaddieren. 
Meine mathematische Intuition sagt mir jedoch, daß dabei genau das 
gleiche rauskommt ;-) Übung als Hausaufgabe.

Beachte daß O (Landau-Symbol) eine Menge beschreibt.

Das 2^n kommt daher, daß die äussere Schleife i.w. n für Zweierpotenzen 
bis N durchläuft, d.h. 2^n läuft bis log(N).

Die Teilmenge ist eine Abschätzung, d.h. alle Funktionen die in der 
einen Komplexitätzklasse liegen, liegen auch in der anderen; aber nicht 
unbedingt umgekehrt.  Vielleicht kann man das auch einfach zeigen, indem 
man einen expliziten Ausdruck für

$$\sum n\cdot 2^n$$

herleitet. War mir an der Stelle zu viel ;-)

[Arc N. (arc)]

Dann mal von vorne

int sum = 0;
for(int n = N; n > 0; n /=2)
    for(int i = 0; i < n; i++)
        sum++;

(ld x = log_2 x = log x / log 2)

Nullte Runde
Aussen: n = N
Innen geht i von 0 bis N - 1 -> Laufzeit c * N/1
(c = Konstante, Addition/Subtraktion/Multiplikation/Vergleiche = 1)

Erste Runde
n = N/2
Innen geht i von 0 bis (N/2 - 1) -> Laufzeit c* N/2

Zweite Runde
n = N/4
Innen geht i von 0 bis (N/4 - 1) -> Laufzeit c * N/4
usw.
Der Bruch kann auch als N/2^r geschrieben werden, r = aktuelle Runde
Abbruchbedingung der äußeren Schleife: n <= 0
Wie viele Runden R gibt's?
Beispiel: N = 16 { 16, 8, 4, 2, 1 }, 8 = { 8, 4, 2, 1 } -> R = ld(N) + 1
Gesamtlaufzeit ist dann:
sum r= 0 to R { c * N/2^r } = c  N  sum r = 0 to R { 1/2^r }
die Summe kann man zu (4 * N - 1) / 2 N vereinfachen...
Einsetzen c  N  4 * (N - 1) / 2 N = 2  c  (N - 1) (Größenordnung 
passt).
D.h. ?

Falls ich mich nicht vertan habe, ist die Laufzeit im dritten Fall:

int sum = 0;
for(int i = 1; i < N; i*= 2)
   for(int j = 0; j < N; j++)
       sum++;

c * (2N + N (ld(N) - 2))

[Johann L. (gjlayde)]

Wieso nimmt du an daß eine Addition konstante Zeit braucht, also O(1) 
ist?
Das ist nur der Fall für kleine Zahlen, d.h. wenn man voraussetzen kann 
daß n < n0 für das Problem, was aber nicht der Fall ist.

Wenn eine obere Schranke für N gegeben istm ist alles on O(1), seh ich 
aber nicht in der Aufgabenstellung.

Bei Komplexitätsanalyse hat man es nicht unbedingt mit "kleinen" Zahlen 
zu tun. Beispiel: Faktorisierung ganzer Zahlen, Diskreter Logarithmus, 
Arithmetik (zB Zahlen mit mehr als 1000 Dezimalstellen), etc.

[Läubi .. (laeubi)]

Ich glaube bei dem Datentyp int darf man schon noch von konstanter zeit 
ausgehen für ein Inkrement

[Arc N. (arc)]

Johann L. schrieb:
> Wieso nimmt du an daß eine Addition konstante Zeit braucht, also O(1)
> ist?
> Bei Komplexitätsanalyse hat man es nicht unbedingt mit "kleinen" Zahlen
> zu tun. Beispiel: Faktorisierung ganzer Zahlen, Diskreter Logarithmus,
> Arithmetik (zB Zahlen mit mehr als 1000 Dezimalstellen), etc.

Kommt drauf an...
Beispiel: Sortieralgorithmus O(n * log n), die Komplexität hängt von der 
Anzahl der Elemente und von der Laufzeit des Vergleichs ab. Solange die 
Laufzeit/Komplexität des Vergleichs nicht von der Anzahl der Elemente 
abhängt (=konstant), ändern sich die Komplexität des Sortieralgorithmus' 
nicht.

[Johann L. (gjlayde)]

Läubi .. schrieb:
> Ich glaube bei dem Datentyp int darf man schon noch von konstanter zeit
> ausgehen für ein *Inkrement*

Ok, damit ist die Aufgabe trivial: alles ist O(1).

Zudem hab ich den Inkrement überhaupt nicht erwähnt oder berücksichtigt; 
die Berechnung von sum hingegen schon.

[Ghost (Gast)]

@ Arc Net

Mir ist die Vereinfachung der Summe nicht ganz klar: Die Summe soll 
vereinfacht werden zu:

Arc Net schrieb:
> (4 * N - 1) / 2 N

Weiter hinten steht:

Arc Net schrieb:
> 4 * (N - 1) / 2 N

Das widerspricht sich doch, oder?

$$\frac{4N-1}{2N} \neq \frac{4(N-1)}{2N}$$

.

Bis hierhin ist mir jedoch alles klar:
Arc Net schrieb:
> sum r= 0 to R { c * N/2^r } = c  N  sum r = 0 to R { 1/2^r }

Aber die geometrische Reihe

$$\sum \limits_{r = 0}^{R} \frac{1}{2^r}$$

 würde ich anders vereinfachen (siehe Anhang, da das mit LaTeX hier 
irgendwie nicht funktioniert hat). Wie kommt man auf deine 
Vereinfachung?

[Arc N. (arc)]

Ghost schrieb:
> @ Arc Net
>
> Mir ist die Vereinfachung der Summe nicht ganz klar: Die Summe soll
> vereinfacht werden zu:
>
> Arc Net schrieb:
>> (4 * N - 1) / 2 N
>
> Weiter hinten steht:
>
> Arc Net schrieb:
>> 4 * (N - 1) / 2 N
>
> Das widerspricht sich doch, oder?

$$\frac{4N-1}{2N} \neq > \frac{4(N-1)}{2N}$$

.

Stimmt...
(4 N - 1) / 2 N wäre korrekt gewesen.

Zweiter Versuch

int sum = 0;
for(int n = N; n > 0; n /=2)
    for(int i = 0; i < n; i++)
        sum++;

Die innere Schleife läuft immer von 0 bis n - 1 d.h. sum++ wird n mal 
ausgeführt
In der nullten Runde von N/1 mal
In der ersten Runde von  N/2 mal
In der zweiten Runde von N/4 mal usw.
Wie oben also N/2^r
Anzahl der Runden R = ld(N) + 1 und da schlich sich dann der Fehler ein:
Beispiel: N = 16 -> R = 5 und die Summe, wie sie oben steht, würde für r 
= 0, 1, 2, 3, 4, 5 berechnet...
D.h. die korrekte Summe ist
sum r = 0 to ld(N) { N/ 2^r }
und es kommt das korrekte Ergebnis 2N - 1 raus.

> Bis hierhin ist mir jedoch alles klar:
> Arc Net schrieb:
>> sum r= 0 to R { c * N/2^r } = c  N  sum r = 0 to R { 1/2^r }
>
> Aber die geometrische Reihe
>

$$\sum \limits_{r = 0}^{R} \frac{1}{2^r}$$

 würde ich anders
> vereinfachen (siehe Anhang, da das mit LaTeX hier irgendwie nicht
> funktioniert hat). Wie kommt man auf deine Vereinfachung?

Da ich faul war aus dem Bronstein ISBN 3-8171-2015-X...
sum r = 0 to ld(N) { N/ 2^r } also N/2^0 + N/2^1 + N/2^2 ...
Für die Summe gilt sn = a0 * (q^(n+1) - 1) / (q - 1)
a[0] = N, q = a[i+1]/a[i] = 1/2 = const
n+1 ist ld(N)+1 und q^(n+1) somit 0.5^(ld(N)+1) = 0.5/N
sn = N * (0.5/N - 1) / (0.5 - 1) = 2 N - 1

[Ghost (Gast)]

Warum komme ich dann mit meiner Betrachtung nicht zum Ziel?
Ist da irgendwo ein Fehler (siehe Anhang)

[Ghost (Gast)]

Oh, sorry, ist ja das gleiche. 2^R ist N. Mein Fehler. Leider kann ich 
nichts editieren