Komplexität
-
Dieser Beitrag wurde gelöscht!
-
@EinNutzer0 sagte in Komplexität:
also ist die Komplexität n log(n)
Nein, die Schlußfolgerung ist falsch.
Es istn * log(n) * log(n)
, also kurzn * log²(n)
.
-
@Mechanics sagte in Komplexität:
Geht schon, hab den irgendwann über unser 6 Mio Zeilen Projekt laufen lassen. Bestimmte Sachen dauern damit schon recht lang. Der Nutzen dieser Analysen und Kompexitätsmetriken ist aber sehr fragwürdig.
Man sollte es nicht als Dogma sondern nur als Orientierung sehen. Dann passt das schon.
-
@Th69 sagte in Komplexität:
Nein, die Schlußfolgerung ist falsch
WolframAlpha sagt mir da aber etwas anderes... Man sollte nicht vergessen, daß es hierbei um die asymptotische Komplexität geht
-
Was war denn deine Anfrage an WolframAlpha?
-
@EinNutzer0: Auch WolframAlpha sieht es so: O(n) * O(log(n)) * O(log(n))
Edit: Shellsort hat z.B. auch als "worst-case performance (with best known gap sequence)" diese Komplexität (da wird also auch nicht ein
log(n)
wegeliminiert - warum auch? Multiplikationen vonN
abhängigen Faktoren bleiben erhalten).
-
Ihr könnt das doch testen.
int func(unsigned n) { unsigned loops = 0; for (int i = n; i > 0; i /= 2) { for (int j = 1; j < n; j *= 2) { for (int k = 0; k < n; k += 2) { loops++; } } } return loops; }
... dann vergleicht func(n) mit n*log(n)*log(n).
Das passt etwa. Es gibt zwar eine leichte Abweichung, aber bei steigenden n's ist der Output proportional. (Ich hab's mit n = 10, 100, 1000 und 10000 probiert).
-
Über die Definition von O (https://de.wikipedia.org/wiki/Landau-Symbole#Definition) lässt es sich auch einfach beweisen das log(n) nicht weglassen werden darf:
Für n -> Unendlich: f(n) / g(n) = (n * log(n) * log(n)) / (n * log(n)) = log(n) < Unendlich
log(n) strebt aber gegen Unendlich und damit ist die Definition nicht erfüllt.
-
@Th69 sagte in Komplexität:
Auch WolframAlpha sieht es so: O(n) * O(log(n)) * O(log(n))
Ich verstehe nicht, wieso Du / 2 einfach unter den Tisch kehrst...
Ihr könnt das doch testen
Das hat mit der asymptotischen Komplexität nur wenig zu tun, zum Vergleich heranziehen müsste man noch mindestens zwei weitere
f(n) / g(n) = (n * log(n) * log(n)) / (n * log(n))
siehe oben
-
/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?