Komplexität
-
/2 ist halt eine konstante und weil konstanten nicht weiter beachtet werden, bzw. trotzdem ein linearer anstieg (nur eben von 1/2 und nicht von 1 oder 100 oder sonstwas) vorhanden ist, ist das O(n)
-
@EinNutzer0 sagte in Komplexität:
Ihr könnt das doch testen
Das hat mit der asymptotischen Komplexität nur wenig zu tun,
Das ist zwar nicht so richtig "mathematisch", aber zur Überprüfung geht es doch. Nimmste diesen aufsummierten Zähler aus der C-Funktion und die Funktion 'f(n) = n * log(n) * log(n)', dann sind beide Kurven ähnlich, sprich gleicher Steigungsverlauf. Jedoch n*log(n) reicht nicht, bzw. verläuft flacher.
-
@EinNutzer0 sagte in Komplexität:
f(n) / g(n) = (n * log(n) * log(n)) / (n * log(n))
Auf der rechten Seite bleibt nur log(n). n*log(n) kannst du doch wegkürzen. Oder nicht?
-
Ich möchte nicht unnötig angeben, aber WolframAlpha widerspricht mir nicht:
https://www.wolframalpha.com/input/?i=O(log_2(n)*log_2(n)*(n%2F2))
-
ja du hast ja prinzipiell auch recht, aber konstanten fallen trotzdem raus, weil es eigentlich egal ist, ob der algorithmus n-mal oder n/2-mal oder 100*n-mal läuft. die komplexität verhält sich linear zu n.
genauso ist es eigentlich auch egal, ob die komplexität O(log(n)) oder O(ln(n)) oder O(log_x(n)) ist, weil du jeden logaritmus zur basis x über einen konstanten faktor in einen logarithmus zur basis y umwandeln kannst.
-
@EinNutzer0 sagte in Komplexität:
Ich möchte nicht unnötig angeben, aber WolframAlpha widerspricht mir nicht:
https://www.wolframalpha.com/input/?i=O(log_2(n)*log_2(n)*(n%2F2))
Das ist doch auch O(n * log²(n)) und nicht O(n * log(n)). Wolfram hat nur von Logarithmus zur Basis 2 auf den natürlichen Logarithmus umgerechnet.
-
@EinNutzer0 sagte in Komplexität:
Ich möchte nicht unnötig angeben, aber WolframAlpha widerspricht mir nicht:
https://www.wolframalpha.com/input/?i=O(log_2(n)*log_2(n)*(n%2F2))
Das unterm Bruchstrich ist 0.9609, fast 1. Und konstante Faktoren fliegen sowieso raus, wie hier schon mehrfach erwähnt wurde.
-
- Offensichtlich kann Wolfram Alpha auch mit der O-Notation nichts anfangen. Es lässt Konstanten drin und kann sowas wie
O(n)*O(n)
nicht zusammenfassen. - Ob du nun , oder oder eine andere Basis nimmst, ist irrelevant (Umformen -> entspricht Multiplikation mit einer Konstanten)
- Offensichtlich kann Wolfram Alpha auch mit der O-Notation nichts anfangen. Es lässt Konstanten drin und kann sowas wie
-
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?