Komplexität
-
Sorry, ja stimmt ich habe nicht nachgedacht... Um bei der Wahrheit zu bleiben weiß ich jetzt nicht mehr genau, was richtig ist...
Es gilt (zumindest bei WA):
log_2(n)*log_2(n)*(n/2)
==O(log_2(n)*log_2(n)*(n/2))
== ... , d h , mit der O-Notation kann WA anscheinend (noch) nicht so viel anfangen.... Von der Falschheit meiner Komplexitätsbestimmung habt ich mich aber auch noch nicht überzeugt.
-
@EinNutzer0 sagte in Komplexität:
Von der Falschheit meiner Komplexitätsbestimmung habt ich mich aber auch noch nicht überzeugt.
Für das Rechnen mit Big-O gelten bestimmte Rechenregeln. So werden bei verschachtelten Schleifen (dein Beispiel), die einzelnen O(x) multipliziert. In deinem Fall also: O(log(n))*O(log(n))*O(n) = O(log(n)*log(n)*n).
Hättest du hingegen die 3 Schleifen hintereinander, wäre das eine Addition, respektive: O(log(n))+O(log(n))+O(n) = O(n). (Das aggressivste O dominiert alle anderen).
-
@kolwe96 Sind nun noch iewelche Fragen offen?
-
Ja
Quasi zurück zum Anfang: Wieso taucht da überhaupt ständig ein Logarithmus auf?..Und wie/wann/warum bricht die erste Schleife überhaupt ab? i>0 ist doch keine Abbruchbedingung..
-
@Progressive sagte in Komplexität:
uasi zurück zum Anfang: Wieso taucht da überhaupt ständig ein Logarithmus auf?..
Und wie/wann/warum bricht die erste Schleife überhaupt ab? i>0 ist doch keine Abbruchbedingung..Doch sicher, die erste Schleife teilt immer durch 2. Also z.B. i=17, i=8, i=4, i=2, i=0 (ist nicht mehr >0, also Abbruch). Und wieso sollte i>0 keine Abbruchbedingung sein?
-
@Progressive sagte in Komplexität:
Quasi zurück zum Anfang: Wieso taucht da überhaupt ständig ein Logarithmus auf?..
Linear Time vs. Logarithmic Time — Big O Notation
@Progressive sagte in Komplexität:
i>0 ist doch keine Abbruchbedingung..
No-na, was sonst?
-
@wob sagte in Komplexität:
@Progressive sagte in Komplexität:
uasi zurück zum Anfang: Wieso taucht da überhaupt ständig ein Logarithmus auf?..
Und wie/wann/warum bricht die erste Schleife überhaupt ab? i>0 ist doch keine Abbruchbedingung..Doch sicher, die erste Schleife teilt immer durch 2. Also z.B. i=17, i=8, i=4, i=2, i=0 (ist nicht mehr >0, also Abbruch). Und wieso sollte i>0 keine Abbruchbedingung sein?
Wann wird denn i=0 erreicht??
2/2 = 1, 1/2 = 1/2, 1/2 / 2 = 1/4,.. das geht doch nie auf Null.@Swordfish sagte in Komplexität:
@Progressive sagte in Komplexität:
Quasi zurück zum Anfang: Wieso taucht da überhaupt ständig ein Logarithmus auf?..
Ich sehe da nicht, warum die Schleife log(n) sein soll. Weil immer halbiert wird?
-
@Progressive sagte in Komplexität:
2/2 = 1, 1/2 = 1/2, 1/2 / 2 = 1/4,.. das geht doch nie auf Null.
Du rechnest mit integern. Schon 1/2 ist 0.
@Progressive sagte in Komplexität:
Ich sehe da nicht, warum die Schleife log(n) sein soll. Weil immer halbiert wird?
Dann lies den Artikel nocheinmal und vielleicht auch den darin verlinkten Artikel "Beginner’s Guide to Big O Notation".
-
@Swordfish sagte in Komplexität:
@Progressive sagte in Komplexität:
2/2 = 1, 1/2 = 1/2, 1/2 / 2 = 1/4,.. das geht doch nie auf Null.
Du rechnest mit integern. Schon 1/2 ist 0.
-
@Progressive sagte in Komplexität:
Ich sehe da nicht, warum die Schleife log(n) sein soll. Weil immer halbiert wird?
Wenn die Schleifenvariable immer halbiert wird, brauchts bei einer Verdopplung des Endwertes bloß nur einen Schleifendurchlauf mehr als zuvor.
2 -- 1
4 -- 2
8 -- 3
16 -- 4
32 -- 5
...usw.Links ist der Endwert und rechts die Anzahl der Schleifendurchläufe. Zufälligerweise sind die Werte auf der rechten Seite der Zweierlogarithmus der linken Seite. Also: logarithmischer Anstieg.
-
@Progressive sagte in Komplexität:
@RBS2 sagte in Komplexität:
Zufälligerweise sind die Werte auf der rechten Seite der Zweierlogarithmus der linken Seite.
Zufälle gibts
-
@Swordfish sagte in Komplexität:
@Progressive sagte in Komplexität:
@RBS2 sagte in Komplexität:
Zufälligerweise sind die Werte auf der rechten Seite der Zweierlogarithmus der linken Seite.
Zufälle gibts
Hexerei!
@Progressive Verständnisfrage: angenommen du musst eine quadratische Matrix (2D-Feld, Breite=Höhe) abklappern, also jedes Element ein Mal ansprechen. Mit welcher Laufzeitkomplexität hast du dann zu tun?
-
@RBS2 sagte in Komplexität:
@Swordfish sagte in Komplexität:
@Progressive sagte in Komplexität:
Hexerei!
Ja, das war Photoshop.
-
@Swordfish sagte in Komplexität:
@Progressive sagte in Komplexität:
i>0 ist doch keine Abbruchbedingung..
No-na, was sonst?
eine durchlauf- oder ausführungsbedingung natürlich......
@Progressive sagte in Komplexität:
Ich sehe da nicht, warum die Schleife log(n) sein soll. Weil immer halbiert wird?
weil ld(2^(n+1)) == n + 1, was heißt, wenn sich die anzahl der ausführungen verdoppelt, wenn n um 1 erhöht wird, ist das ganze logarithmisch.
dabei macht es natürlich keinen unterschied, ob du 1 immer mit 2 multiplizierst, bis du 64 hast, oder 64 immer durch 2 teilst, bis zu 1 hast.edit: allgemein ist die komplexität natürlich lagorithmisch, wenn sich die ausführungszeit um einen konstanten faktor, welcher der basis des logarithmus entspricht, erhöht. d.h. wenn du n um 1 erhöhst und sich die ausführungszeit "ver-x-facht" hast du halt einen logarithmus zur basis x.
-
-
@RBS2 sagte in Komplexität:
Hexerei!
@Progressive Verständnisfrage: angenommen du musst eine quadratische Matrix (2D-Feld, Breite=Höhe) abklappern, also jedes Element ein Mal ansprechen. Mit welcher Laufzeitkomplexität hast du dann zu tun?
Im Zweifel immer O(1). Ich packe jede Matrix dieser Form einfach in eine größere Matrix mit
numeric_limits<size_t>::max()
Elementen und klappere einfach in dieser jedes Element einmal ab. Ist viel schneller, sagt mir meine Laufzeitanalyse. SCNR