Asymptotische Laufzeit eines Algorithmusses

[Astasor]

Hey, ich bins nochmal.

ich arbeite gerade an der asymptotischen Laufzeit von Algorithmen.

Muss ich da nur die Befehlsaufrufe zählen oder noch mehr?

Angenommen ich hätte folgenden Algorithmus

for j=wert to endwert do   

{

wertzuweisung; 

arithmetische Operation;

while schleife(Bedingung) { lustiger schleifeninhalt aus einzeloperationen}

noch ne wertzuweisung;

}

angenommen die bedingung trifft niemals zu.

da läuft die for schleife doch n-mal durch und die anderen operationen (n-1) mal.

n+4*(n-1), oder?

wie muss ich die while schleife gewichten? einzelne operationen sind ja immer O(1).

ich habe gelesen, das ich bei dem schleifeninhalt von while schleifen, die ausführung durch die befehlsanzahl teilen muss. stimmt das?

mfg Astasor

[flashpixx]

ich habe gelesen, das ich bei dem schleifeninhalt von while schleifen, die ausführung durch die befehlsanzahl teilen muss. stimmt das?

Das macht keinen Sinn, denn damit würdest Du nur einen Bruchteil der eigentlichen Laufzeit erhalten.

Eine Schleife wird n mal durchlaufen, wobei n >= 0 und natürliche Zahl ist. Somit werden die Befehle innerhalb der Schleife n mal ausgeführt, d.h. dann n * O(<Komplexität der Schleife>), da eine Schleife linear zur Laufzeit beiträgt. Je nach Schleife muss man dann schauen ob es n oder n-1 ist.

Du musst eben für das Landau-Symbol die Anzahl der Durchläufe ermitteln und vorher beweisen, dass die Schleife terminiert, da sonst die Laufzeit divergieren kann.

Bearbeitet 17. November 2010 von flashpixx

[Astasor]

Danke für die Antwort und deine Begründung ist einleuchtend.

vorher beweisen, dass die Schleife terminiert

wie mache ich das?

per Induktion?

oder einfach in dem ich allgemeingehaltene eingabefolgen abarbeiten?

oder per gegenbeweis? (müsste möglich sein, indem ich annehme das die schleife nicht terminiert und mir die anweisungen in der schleife ankucke.)

oder einfach indem ich die befehle in der schleife gegen unendlich bei gegebenen eingaben durchlaufen lasse und schau was passiert?

ich fühl mich als ob ich hier ein brett vorm kopf hätte, dann ich weis nicht, welche meiner überlegungen sind richtig und welche nutzlos.

annahme: while schleife mit (Bedingung: zahl<n) terminiert nicht.

folgerung: bei gegebenen Eingaben läuft die schleife undendlich lang.

Beweis: zahl wird bei jedem schleifendurchlauf um 1 erhöht.

Widerspruch: die bedingung gilt nicht für jede belegung von zahl. q.e.d.

Änderung:

im bestcase - wenn die while <Bedingung> immer false ergibt, läuft der schleifeninhalt der forschleife genau n mal durch.

d.h.: die while-schleife hat einen null aufwand und der ist konstant

Ergebnis: n*O(1)

ergibt die while bedingung nun mal true, dann läuft der schleifeninhalt durch und die while bedingung wird wieder aufgerufen.

also ist die komplexität der whileschleife (n+Anzahl der While-Schleifendurchläufe), oder?

[flashpixx]

wie mache ich das?

Schleifeninvariante ? Wikipedia

Je nach While-Schleifen-Inhalt bietet es sich an, das ganze nicht iterativ, sondern rekursiv zu formulieren: Wenn Du z.B. den Schleifenrumpf als Induktion von n nach n-1 auffassen kannst, ist es einfacher das ganze zu beweisen (in diesem Fall hättest Du ja nur n Aufrufe).

[Astasor]

neue Frage aber gleiches Thema, deswegen alter Thread.

wenn ich teile eines Algorithmusses habe, die mit O(n) Zeit laufen und Teile die mit O(log n) Zeit laufen, wie lautet dann die Gesamtlaufzeit?

O(n*log n)?

mfg Astasor

[flashpixx]

wenn ich teile eines Algorithmusses habe, die mit O(n) Zeit laufen und Teile die mit O(log n) Zeit laufen, wie lautet dann die Gesamtlaufzeit?

O(n*log n)?

Das kann man nicht generell beantworten, denn es kommt darauf an, wie die "Teile" verbunden sind, siehe dazu die Rechenregeln der Landau-Symbole

[Astasor]

Danke für deine Hilfe, flashpixx, doch hier mal das genaue Problem. Und mit Rechenregeln, meinst du da die mathematische definition oder was man macht, wenn man T(n)= 3T(n/4)+O(n) vorgesetzt bekommt und das dann einordnen soll?

ich will zwei Rot-Schwarz-Bäume vereinigen, so dass ein Rot-Schwarz-Baum ausgegeben wird, der alle Elemente enthält.

hier mal mein Algorithmus in Pseudocode, der sehr stark an Java angelehnt ist. Die Prozedur für das Einfügen in einen RS-Baum habe ich jetzt mal weggelassen, da bekannt ist, das dass Einfügen und Reparieren in solch einen Baum zusammen O(log n) im worst case brauch.

int getBH(T){ //Bestimmung der BH um herauszufinden, welcher Baum größer ist. O(log n)

//T RS-Baum   


Node tmp<- root[T]

int bh<-1


while (tmp.left!=null){


tmp.left

if (tmp.color=black) then bh=bh+1


}

return bh

}


preOrder( x,T ){  //x knoten, wurzel wird zuerst in den größeren Baum eingefügt, dann der Rest


    RSinsert(T,x) O(logn)  //einfügen in einen Rot-Schwarz Baum O(log n)


    if knoten.links ≠ null then  //pre Order durchlauf O(n), da alle Knoten angeschaut werden müssen

        preOrder( knoten.links )


    if knoten.rechts ≠ null then

        preOrder( knoten.rechts )

}


vereineRstrees(T1,T2){


Node tmp


if (getBH(T1)>getBH(T2)) then{

tmp<-root[T2]

preOrder(x,T1)   //einfügen von T2 in T1

return T1

}



else{ 

tmp<-root[T1]

preOrder(x,T2)   //einfügen von T1 in T2

return T2

}

}

Mit so was tue ich mich noch schwer. Doch es gibt auch keine guten Bücher über das Laufzeitverhalten.

mfg Astasor

Bearbeitet 13. Dezember 2010 von Astasor

[flashpixx]

Und mit Rechenregeln, meinst du da die mathematische definition oder was man macht, wenn man T(n)= 3T(n/4)+O(n) vorgesetzt bekommt und das dann einordnen soll?

Wenn T(x) eine Funktion ist, kannst Du die rekursive Definition auflösen und entsprechend den Aufwand abschätzen.

Doch es gibt auch keine guten Bücher über das Laufzeitverhalten.

Man kann die Landau Klasse durch einen Limes ohne Probleme ermitteln, der Rest ist mathematisches Umformulieren. Ansonsten wäre wohl Priese&Erk mit "Eine Einführung in die theoretische Informatik" bzw. Robert Sedgewick mit "Algorithmen" die passenden Einstiegswerke.

Das Umformen einer Rekursionsgleichung sollte bei den Landau Klassen bekannt sein.

[Astasor]

mit abschätzen meinst du sicherlich diese methode?

Substitutionsmethode

mfg Astasor

[flashpixx]

Ist eine Möglichkeit, da Du ja immer nur den Limes betrachtest. Je nach Gleichung kannst Du aber die Rekursion zu einer Iteration umformulieren und dann direkt den Aufwand bestimmen, denn jeder iterative Algorithmus lässt zu einem rekursiven und umgekehrt umformulieren.