(Twitter)
[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.
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:
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?!
Schüler, Punkte: 455
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)
─ sven03 24.04.2021 um 11:38Auch 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 :)