|
Anzeige
|
Komplexität eines Algorithmus bestimmen
Gast
#2378419
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?
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? 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: Dann ist 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 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 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 istFür drei Schleifen hab ich grad keine Lust es auszurechnen, aber ich vermute stark dass da dann etwas mit n³ steht.
Gast
#2379351
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 > > > 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. 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: Die letzte Umformung ist die allseits beliebte Gaußsche Summenformel (siehe Wikipedia). Antwort schreibenBitte melde dich an, um einen Beitrag zu schreiben. |
Anzeige
|
