Laufzeitanalyse/Komplexitätsklasse

[hanschris0]

Hallo erstmal,
bei mir stehen in einen Monat Prüfungen an und ich verstehe nicht so genau wie man die Laufzeit bestimmen kann.

Als einfaches Beispiel

for (int i=0; i < n; i++)
for (int j=0; j < n; j++) count++;

Die äußere Schleife läuft n mal durch und ebenso verhält sich das mit der inneren Schleife. Als Laufzeit wäre das O(n^2). Das habe ich soweit verstanden.


Nun wäre noch die Beispiele unklar

for (int i=0; i < n; i++)
for ( i=0; i < n; i+=2)
count++;

Äußere wird n mal durchlaufen also O(n)
die innere läuft dann O(n/2) also insgesamt O(n^2/2)? Da Konstanten wegfallen kann ich dann einfach 0(n^2) schreiben?

Wenn ich den Code nun so ändern würde zu

[code]for (int i=1; i < n; i*=5)
for (int j=0; j < n; j++) count++;

[/code]

Bei der äußeren weiß ich nicht genau wie ich das hier machen soll.
Die innere Schleife wäre hier einfach nur O(n).


Dann der Gauß:

for (int i=n; i > 0; i--)
for (int j=i; j < n; j++)
count++;

Äüßere Schleife läuft einfach rückwärts also O(n)
bei der innere Schleife weiß ich nicht wie ich das erkennen soll.
Laufzeit wäre hier N/2*(n-1)

Könnte mir jemand eine kurze Erklärung geben wie man solche Laufzeiten zügig erkennt weil in den Klausur hat man pro Bestimmung auch nur 1 Minute Zeit und ich verstehe nicht so genau wie man so schnell draufkommt.

 

[Xyz1]

Niemand sollte mit 2 Jahren schon studieren. Lass Dir noch ein wenig Zeit.

 

[Javinner]

wie man die Laufzeit bestimmen kann.

?!

 

[Hutzli]

Also ich muss sagen, dass ich diesbezüglich nicht so sattelfest bin, aber deine 3. Aufgabe würde ich mal so angehen:
i = 5^k

i < n
=> 5^k < n
=> k < log_5(n)
=> Äussere Schleife: O(log_5(n)) : Innere Schleife: O(n)
=> O(log_5(n)) * O(n) = O(n * log_5(n))

 

[mihe7]

bei der innere Schleife weiß ich nicht wie ich das erkennen soll.

Wenn es einfach gehen soll: im Inneren wird count bei jedem Schritt immer nur um eins hochgezählt. Die Schrittzahlfunktion kann somit nicht wesentlich schneller wachsen wie die Funktion, mit der count beschrieben werden kann. Und da man die meist kennt...

Die allgemeinere Variante: im Innern werden nur eine konstante Zahl von Operationen ausgeführt, also O(1). Diese werden - aufrund der inneren Schleife - offensichtlich (n-i)-mal ausgeführt. Das i geht aufgrund der äußeren Schleife von 1 bis n.
D. h. insgesamt

\sum_{i=1}^n (n-i) = \sum_{i=0}^{n-1} i 
  = \sum_{i=1}^{n-1} i 
  = n*(n-1)/2
  = (n^2 - n)/2

Konstanten raus: O(n^2 - n) bzw. O(n(n-1))