Laufzeitkomplexität bestimmen

Aufrufe: 338     Aktiv: 24.04.2021 um 14:16

0

Ich weiß nicht, ob mir jemand helfen könnte, aber ich bin momentan maßlos überfordert bei Bestimmung der Laufzeitkomplexität in Abhängigkeit des Rückgabewerts n. Theoretisch müsste es ja so sein, wenn ich eine einfache Schleife von i <- 0 bis n - 1 habe, dann sei die Laufzeitkomplexität n, wenn sie verschachtelt ist, wird die Laufzeit in O Notation Quadratisch. Ganz genau: for i <- 0 bis n verschachtelt mit for k <- 0 bis n wäre n * n, also O(n²) bzw. for i <- 0 bis n und for k <- i bis n, (n) * ( n -1) * (n -2 ) bis (n), wäre die Gauß'sche Summenformel und wiederrum in O(n²) Wenn man eine Schleife for i <- 0 bis n hätte, sich aber mit i z.B. über 2i pro Iteration annähert, dann wäre die Komplexität log_2(n) (die Laufzeit wird ja weniger) Hierzu mein Beispiel enter image description here [Quelle TU Wien] Da wäre die Überlegung wiederrum man nähert sich mit 2er Schritte an, d.h. log_2(4^(n)), nur die Lösung sagt, dass es sich hierbei um die Komplexität O(n³) handelt - ich kenne mich trotz mittlerweile Lesens von zwei Büchern, in denen das leider auch nicht entsprechend erklärt wird, überhaupt nicht aus und wäre sehr dankbar, wenn mir jemand helfen könnte bzw. Quelle nennen könnte, wo man die Errechnung der Laufzeitkomplextität (kein zu großer "zu einfacher" theoretischer Input - der mir nur erklärt, was Schranken sind, usw. - vielleicht mit Beispielen, wo so etwas (in schwieriger Form) (nicht wo erklärt wird, wie man die Komplexität einer einfachen Schleife ausrechnet) erklärt bekomme könnte.

Vielen, vielen Dank schon mal :)

gefragt

Punkte: 14

 
Kommentar schreiben
2 Antworten
1

Die Frage, die du dir stellen musst, ist ja: Wie viele Schritte sind notwendig, um bei gegebenem n auf 4^n zu kommen, wenn ich bei 1 anfange und bei jedem Schritt verdopple. Das klassische Beispiel ist ja die Grenze n, wobei du dann log(n) Schritte brauchst, so dass die Laufzeit bei einer Schleife folgender Form:

i = 1
while i <= n
   i = 2i

in O(log n) liegen würde. Der gegebene Algorithmus hat aber das Ende bei 4^n, weshalb sich jetzt eben die anfangs erwähnte Frage stellt. Wenn du einfach mal n, 4^n und log(4^n) nebeneinander aufträgst, hast du schon mal ein Gefühl dafür in welche Richtung es gehen könnte:

enter image description here

Die dritte Spalte definiert bei gegebenem n, die Anzahl der Schritte (also Schleifendurchläufe), um zu dieser Grenze 4^n zu kommen und wie du siehst, wächst die Anzahl der Schritte linear mit n, daher würde ich eigentlich sagen, dass die Laufzeit in O(n) liegt. Warum in der Lösung O(n^3) liegt ist mir auch ein Rätsel, vielleicht habe ich einen Denkfehler drin?!

Diese Antwort melden
geantwortet

Schüler, Punkte: 450

 

Vielen, vielen, vielen Dank - mehr fällt mir dazu nicht ein :) Theoretisch sind mir die Grundlagen ja geläufig (das sehe ich dann wie bei der WS Rechnung) - zumindest multiplikativ - wenn zwei Schleifen ineinander verschaltet werden und die erste bis n läuft, dann haben wir eine Gesamtlaufzeit von n * wie oft die zweite (ganz banal)
Auch war mir eigentlich klar, dass man sich immer Fragen sollte, wie schnell näher ich mich mit veränderten, bzw. unveränderten Ziel an (in dem Fall eigentlich mit 2^(n) -> 4^(n)), also darf die Laufzeit nicht wie bei (n -> 4^(n)) (lineare Annäherung => 4^(n) Laufzeit) (je nachdem wie man die Notation wählt, aber der Schritt ist mir glaub ich klar).
Ich muss dir ganz ehrlich sagen, ich weiß nicht, ob die Lösung stimmt - ich habe zwar versucht die Aufgabe zu lösen damals, und dieses Beispiel von jemanden abgeschrieben - dann aber schlauerweise mir in der Übung die Lösung nicht aufgeschrieben. Aber es stand in der Angabe, man solle die Komplexität des Rückgabewertes bestimmen (macht das im allgemeinen Unterschied zur normalen Laufzeit - rein Hypothetisch man hätte zwei Schleifen, ev. sogar eine ineinander verschachtelt, wäre die Komplexität der Rückgabe dann höher, oder auch in O(n²)?
Und da du auf jeden Fall viel mehr Wissen als ich vorzuweisen hast - weißt du vielleicht, wo derartiges gut erklärt wird, in den jetzig gewählten Büchern wird das leider nahezu überhaupt nicht erklärt - YT Tutorials sind eher einfach gehalten (eine Schleife) -meine momentanen Quellen sind: VO Folien (weil auf die Vorlesung verzichte ich nunmehr - kostet viel Zeit und bringt wenig (da lese ich lieber Bücher, macht sowieso mehr Spaß :)), Algorithmen und Datenstrukturen (Ottmann) und Introduction to Algorithms (Cormen)
Vielen Dank nochmal :)

  ─   sven03 24.04.2021 um 11:38

Kommentar schreiben

1

Zu deiner ersten Frage: Nein die Komplexität des Rückgabewertes ist das gleiche, auch wenn es selten so komisch formuliert wird ... Man sagt die eher "Die Laufzeitkomplexität des Algorithmus" oder ähnliches.

Ich kann dir folgendes Buch empfehlen, das man sogar kostenlos im Internet erhalten kann: https://cin.ufpe.br/~fbma/Crack/Cracking%20the%20Coding%20Interview%20189%20Programming%20Questions%20and%20Solutions.pdf

Schau dir einfach das Kapitel "Big O" an, es ist sehr anschaulich erklärt, meiner Meinung nach.

Diese Antwort melden
geantwortet

Schüler, Punkte: 450

 

Danke nochmals, ich hoffe das hilft mir :)

  ─   sven03 24.04.2021 um 14:16

Kommentar schreiben