Hallo, sind gerade dabei, für eine Klausur zu lernen, haben aber noch ein paar Schwierigkeiten. Die Aufgabe lautet: Bestimmen Sie die Zeitkomplexität in Abhängigkeit der Eingabe n (einer positiven ganzen Zahl) der folgenden Algorithmen, wobei die Grundrechenarten, Speicherzugriffe und Vergleiche die Komplexität O(1) haben. Man kann jeweils ankreuzen: O(1), O (log n), O(n), o(n log n), O(n^2), O(n^3), O(2^n) a) int max = a[0]; for (int i = 1; i <n, i++) if (a[i] > max) max = a[i]; b) int k = 0; for (int i = 0, i<n, i++) for (int j = 1; j <4*i, j++) k += j; c) int t = 1 while (t <=n) t = 2*t; d) Aufruf der folgnden Methode mit calc (n) static int calc (int i) { if (i ==0) return 1 return calc (i-1) + calc(i-1); e) Aufruf der folgnden Methode mit isEven(n) static boolean isEven(int i) { switch (i) { case 0: return true; case 1: return false; default: return isEven(i-2); } } Sind folgende Überlegungen ok? a) Die For Schleife wird n-1 mal durchlaufen also O(1). b) Die erste for Schleife hat die Komplexität O(n). Was bedeutet bei der zweiten k+=j? Bekommt nur k einen neuen Wert, dann hat diese Zeile ja keinen Einfluss und die zweite Schleife hat auch O(n) also insgesamt O(n^2). c) log(n). Denn mit zunehmendem n erreicht man dieses zwar immer länger, aber da verdoppelt wird auch relativ schnell ?! Oder wie kommt man auf das Ergebnis, es ist zwar klar irgendwoher, aber wie kann man es exakt bestimmen? d) Andere Frage: wie oft wird die Methode calc (i-1) aufgerufen? Und zwar O(n + n) = O(2n) * O(n) e) Andere Frage: wie oft wird die Methode aufgerufen? zwar immer i-2, aber je größer die Zahl, desto mehr aufrufe also O(n). Also fast immer nur O(n) angekreuzt ?!? Dankeschön ;)
>Sind folgende Überlegungen ok? >a) Die For Schleife wird n-1 mal durchlaufen also O(1). Bist du sicher ? Wie war das nochmals ?
b) ist O(N^2) , die 2.Schleife macht nochmals O(N) durchlaeufe. d) ist eine rekursion (nie gehoert ) damit O(2^N)
Vielen dank für deine Hilfe. b) hab ich ja auch so. Wieso schreibst du u den anderen nichts? Ist dir b und d nur spontan eingefallen, oder stimmt der Rest? Wieso: "d) ist eine rekursion (nie gehoert ) damit O(2^N)" Das verstehe ich nicht. Es wird ja immer eins abgezogen und die Rekursion nochmals aufgeruen. is man bei der 0 ist. Also z.B. n = 5 5 , 4, 3, 2, 1, das ganze passiert zweimal Wie kommt man da auf 2^n?
Jochen wrote: > n = 5 > 5 , 4, 3, 2, 1, > das ganze passiert zweimal Aber für jeden der beiden Teilzweige teilt es sich dann wieder in 2 Teile. > Wie kommt man da auf 2^n? calc(5) / \ calc(4) calc(4) / \ / \ calc(3) calc(3) calc(3) calc(3) / \ / \ / \ / \ calc(2) calc(2) calc(2) calc(2) calc(2) calc(2) calc(2) calc(2) / \ / \ ...... c(1) c(1) c(1) c(1) Bei derartigen Binärbaum Strukturen ist der Trick praktisch immer darin zu suchen, dass du 2^n-1 Knoten in einem Baum mit der Höhe n anordnen kannst. Hier, bei der Komplexitätsanalyse ist es genau umgekehrt: Du hast die Baumhöhe gegeben und willst wissen wieviele Knoten da drinn Platz haben (weil jeder Knoten eine Berechnung darstellt). Bei einer Baumhöhe von n brauchst du daher 2^n-1 Berechnungen. Die -1, als konstanter Anteil, fallen unter den Tisch.
Wenns für ne Übungsaufgabe und nicht für eine Klausur ist, kannst du das Moore'sche Gesetz mit einberechnen: Alle 1,5 Jahre verdoppelt sich die Leistungsfähigkeit der Computer. die Konstante "1.5 Jahre" fliegt in der O-Notation natürlich raus, also wird jeder Rechenschritt in der halben Zeit des vorhergehenden ausgeführt...
Danke für die Zeichnung und den Beitrag :D Wenn bei dieser Aufgabe return calc (i-1) + calc(i-1) + calc(i-1); dort stehen würde, hätte man 3^n, oder? Sind die anderen Aufgaben korrekt? Wie kann man log n erkennen, ich mach das immer nach "Gefühl".
Jochen wrote:
> Wie kann man log n erkennen, ich mach das immer nach "Gefühl".
log n liegt zb dann vor, wenn du in besagtem Baum was suchst.
Wenn also die Suchmenge in 2 Hälften geteilt wird und abhängig
vom Suchparameter entweder die eine Hälfte oder die andere
Hälfte weiter untersucht wird.
n ist die Menge der verfügbaren Knoten.
Log N ist eine binaere Suche, oder ein Quicksort. Man hat einen Aufwand fuer jedes zusaetzliche Bit in der Breite. Und das ist Log2(N)
Bis auf den Tippfehler bei a) stimmt's.
> Ist Quicksort nicht n * log n ?
Ist es. Da muss 6637 was verwechselt haben. Binäre Suche ist aber
wirklich O(log n) sofern der Suchbaum nicht degeneriert ist.
Wenn man Aufgabe b abändert in int k = 0; for (int i = 0, i<n, i++) for (int j = 1; j <4*i, j++) j = j*2 wäre das dann O(n*logn) ?
Das "int k=0" verwirrt mich etwas weil es weiter nicht benutzt wird. Wolltest du vielleicht was anderes schreiben? So wie es jetzt da steht ist es immer noch O(n^2): Die äußere Schleife wird n-mal durchlaufen. Die innere wird 4*(i-1)-mal durchaufen, das sind im Mittel über alle Durchläufe der äußeren Schleife O(n) (*), also insgesamt O(n^2) Durchläufe der inneren Schleife. (*) Mittel {0, 4, 8, 12, ..., 4*(n-2), 4*(n-1)} = 4 * Mittel {0, 1, 2, ..., n-2, n-1} = 4 * Summe {0, 1, 2, ..., n-2, n-1} / n = 4 * (n-1) * (n-2) / (2n) = 2 * (n-1) * (n-2) / n = O(n)
STOP ich ziehe alles zurück, habe die Multiplikation von j in der inneren Schleife übersehen. Leider weiß ich nicht wie man hier im Forum was editieren oder löschen kann.
@Morin: Dass das k nicht mehr benutzt wird, liegt daran, dass ich genau diese Zeile, wo es benutzt wird, verändert habe ;) Danke, für dein Mühe. Stimmt es denn, dass der Aufwand davon O(n logn ) ist?
Hab leider erst jetzt weder Zeit. Also: Die Analyse wird etwas komplizierter, weil in der inneren Schleife das j sowohl verdoppelt als auch pro Durchlauf 1 addiert wird. Das heißt aber dass nach P Durchläufen j = ...2*(2*(2*1+1)+1)+1... = 2^P + 2^(P-1) + 2^(P-2) + ... + 1 = 2^(P+1)-1 <! 4*i und damit alle Durchläufe der inneren Schleife zusammen genommen in O(log i) durchlaufen werden. Also liegt die insgesamt benötigte Zeit in der Ordnung log 1 + log 2 + log 3 + ... + log n = log (n!) Ich bin jetzt allerdings nicht sicher ob O(log (n!)) und O(n*log n) dasselbe sind oder ob ersteres "kleiner" ist.
Nur der Vollstaendigkeit halber: Quicksort ist in O(n^2), aber nicht in O(n log n). Wenn du einen O(n log n)-Sortier-Algorithmus brauchst, musst du etwas anderes nehmen wie zum Beispiel Heapsort. Der Grund ist, dass die Gross-O-Notation eine obere Schranke angibt und keine mittlere Laufzeit. Quicksort wird bei bestimmten (z.B. vorsortierten) Eingabedaten quadratische Laufzeit benoetigen, daher ist Quicksort nicht mehr in O(n log n). Uebrigens: Praktisch jeder uebliche Algorithmus ist in O(n!). Denn O(f) fuer irgendeine Funktion f ist in Wirklichkeit eine Menge mit der Eigenschaft dass sie alle Funktionen enthaelt, die hoechstens so schnell wachsen wie f. Ein Algorithmus der in O(n log n) ist, ist also automatisch auch in O(n^2), O(n^3), O(2^n) und vielem mehr. Wenn die Aufgabe also zum Ankreuzen ist und man korrekt sein will, muss man neben der niedrigsten auch alle hoeheren Schranken ankreuzen. Ansonsten ist das mathematisch gesehen einfach falsch.
Christoph __ wrote: > Nur der Vollstaendigkeit halber: Quicksort ist in O(n^2), aber nicht in > O(n log n). Wenn du einen O(n log n)-Sortier-Algorithmus brauchst, musst > du etwas anderes nehmen wie zum Beispiel Heapsort. > Der Grund ist, dass die Gross-O-Notation eine obere Schranke angibt und > keine mittlere Laufzeit. Quicksort wird bei bestimmten (z.B. > vorsortierten) Eingabedaten quadratische Laufzeit benoetigen, daher ist > Quicksort nicht mehr in O(n log n). Quicksort ist in O(n log n), da n nicht die Art der Eingabedaten bestimmt, sondern nur deren Anzahl (rekursive Laufzeitgleichungen). Will man das ganze auch im Worst-Case in n log n, nimmt man den Median zum partitionieren.
Ok, ich war unpraezise. Dass n die Anzahl der Eingabedaten angibt, ist mir selbstverstaendlich bekannt, wie sollte eine natuerliche Zahl auch die Art der Eingabedaten angeben? Zu Quicksort: Wenn man den Median als Pivot nimmt funktioniert es tatsaechlich in O(n log n), vorausgesetzt man bekommt den Median in linearer Zeit, was nicht ganz trivial ist. Bei meiner Betrachtung oben bin ich von naivem Quicksort ausgegangen, dass zum Beispiel immer das erste Element des Arrays als Pivot benutzt. Dann ist Quicksort in O(n^2), weil es eben Eingabedaten der Laenge n gibt bei denen die Schranke O(n log n) ueberschritten wird.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.