Laufzeit von verschachtelter for-Schleife

[Adrjan]

Hallo zusammen,

ich habe etwas Probleme die Laufzeit von folgendem Schleifenkonstrukt festzustellen, ich gebe das Ganze in Pseudocode an:

for i = 2 to A.length do
Neues Feld B anlegen mit länge von i
     for j = 1 to i do
          B[j] = A[j]
     Aufruf von Sortiermethode, dass Feld B sortiert
     for j = 1 to i do
          A[j] = B[j]

Es gibt eine äußere for-schleife und zwei innere.
Die Laufzeit wäre doch somit (n-1) * [(n-1) + (n-1)] => O(n²) , oder?

Ich bin für jede Hilfe dankbar!

Viele Grüße
Adrjan

 

[Gucky]

Die Laufzeit ist: (Laufzeit der beiden Inneren + Laufzeit der Sortiermethode) mal Anzahl der Durchläufe der Äußeren.

 

[Adrjan]

Vielen Dank für Deine Antwort, ich habe das mir auch so gedacht.
Mir bereitet Probleme, wie ich die Laufzeit der folgenden Schleife berechne:

for j = 1 to i do

Diese geht ja nich durch das gesamte Array, sondern immer nur von 1 bis i, wobei sich i nach jedem äußeren Schleifendurchgang erhöht... Hast Du eine Idee?

 

[Gucky]

Erhöht i sich so lange, bis die Schleife nur noch einmal durchlaufen wird? Wenn ja, dann ist es (n-1)/2, da immer einer weniger durchlaufen wird. Kann man sich mit einem Rechteck und einem Dreieck, welches darin ist vorstellen.

 

[Adrjan]

Danke Dir!
Jep, i wird solange erhöht bis die Schleife nur noch einmal ausgeführt wird.

Ich glaube jetz thabe ich alles kapiert. 🙂