Komplexität eines Algorithmus bestimmen

[Egon (Gast)]

Hallo,

ich habe noch eine Frage und zwar kann mir einer von euch anhand eines 
Beispieles erklären, wie man die Komplexität eines Algorithmus bestimmt?

for i=0 to n-1
     for j=i+1 to n
          for k=i to j
               do s.th.

Hätte man 3 for schleifen, die jeweils die ganze Liste durchgehen, wäre 
es ja O(n^3). Das ist ja aber hier nicht der Fall. Gibt es einen Weg die 
Komplexität formell zu bestimmen?

[Niklas G. (erlkoenig)]

Du berechnest zunächst, wie oft das innere "do sth" ausgeführt wird (in 
Abhängigkeit von n). Das nennst du dann f(n). Dann bestimmst du eine 2. 
Funktion g, sodass gilt:

$$\lim_{n->\infty{}}{\frac{f(n)}{g(n)}} < \infty$$

Dann ist

$$f \in O(g)$$

 bzw. die Komplexität ist O(g).

Für g=n^3 gilt das in deinem Fall ziemlich sicher, daher ist dein 
Algorithmus auf jeden Fall in O(n^3). ich meine zu sehen, dass er in 
keiner "kleineren" Komplexitätsklasse ist.

Guggstu auch da: http://de.wikipedia.org/wiki/Landau-Symbole

[Daniel F. (df311)]

meine komplexitätskenntnisse sind (leider) zum glück nicht mehr 
besonders vorhanden (alkohol sei dank ;-) ). der springende punkt könnte 
aber die zweite und dritte schleife sein, da diese nicht bei i starten, 
also immer kürzer werden...

EDITH: auf dritte schleife erweitert

[Niklas G. (erlkoenig)]

Zumindest, wenn es 2 Schleifen wären, a la
for i=0 to n-1
     for j=i+1 to n
          do sth

Dann wäre es immernoch O(n²), denn die Laufzeit ist

$$\frac{n*(n+1)}{2}=\frac{1}{2}*n^2 + \frac{1}{2}*n$$

Für drei Schleifen hab ich grad keine Lust es auszurechnen, aber ich 
vermute stark dass da dann etwas mit n³ steht.

[Programmierer (Gast)]

Niklas Gürtler schrieb:
> Zumindest, wenn es 2 Schleifen wären, a la
> for i=0 to n-1
>      for j=i+1 to n
>           do sth
>
> Dann wäre es immernoch O(n²), denn die Laufzeit ist
>

$$\frac{n*(n+1)}{2}=\frac{1}{2}*n^2 + \frac{1}{2}*n$$

>
> Für drei Schleifen hab ich grad keine Lust es auszurechnen, aber ich
> vermute stark dass da dann etwas mit n³ steht.



Wie genau hast du denn hier die Laufzeit berechnet? Mein Problem ist, 
dass ich nicht weiß, wie ich die verschachtelten schleifen handhaben 
soll.

Ich habe mich glaube ich auch verschrieben oben:

for i=0 to n-2
      for j=i+1 to n-1
           do sth

muss es heißen.

[Niklas G. (erlkoenig)]

Programmierer schrieb:
> Wie genau hast du denn hier die Laufzeit berechnet? Mein Problem ist,
> dass ich nicht weiß, wie ich die verschachtelten schleifen handhaben
> soll.
Öh, ich glaub ich hab mich um 1 oder 2 vertan, ich bin vom 
"Standardproblem":
for i = 1 to n
     for j = 1 to i
          do sth
ausgegangen, die "verschiebung" darfst du dann selber mit einrechnen:

Für den ersten Durchlauf der äußeren Schleife wird die innere 1x 
ausgeführt, für den 2. Durchlauf de äußeren Schleife 2x, usw, beim n-ten 
Durchlauf der äußeren schließlich n mal. Die Anzahl, wie oft "do sth" 
ausgeführt wird, ist also:

$$1+2+3+ .... + n = \sum_{k=1}^{n}{k} = \frac{n*(n+1)}{2}$$

Die letzte Umformung ist die allseits beliebte Gaußsche Summenformel 
(siehe Wikipedia).