Komplexität
-
@RBS2 Ich nutze den nur für meine eigenen Projekte und die haben selten mehr als 200k Zeilen. Keine Ahnung wie er auf gigantische Projekte reagiert.
-
@It0101 Noch ist er beschäftigt. Schade dass er keine Fortschrittsanzeige hat.
Edit: Immer noch 40% CPU-Auslastung, ca. 3.3MB/s Diskzugriffe.
Ich denke, ich breche den Versuch ab.
-
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.
-
@kolwe96 sagte in Komplexität:
for(int i=n ; i>0 ; i/=2){
log n
for(int j=1 ; j<n ; j*=2){
log n
for(int k=0 ; k<n ; k+=2){
n / 2
also ist die Komplexität n log(n)
-
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.