Komplexität
-
äh nein? Wie kommst du darauf?
Würde jede deiner drei Schleifen von 0 bis < n laufen, hätte das Ding eine Komplexität von O(n^3). Da das deine Schleifen aber nicht tun, musst du die Anzahl der jeweiligen Schleifendurchläufe in Abhängigkeit von
n
ausdrücken.Die äußerste Schleife ist O(log n) die nächste auch, aber die dritte ist O(n/2).
-
@Swordfish sagte in Komplexität:
Die äußerste Schleife ist O(log n) die nächste auch, aber die dritte ist O(n/2).
Was entspricht, und außerdem stützt die Tatsache, dass die ersten beiden logarithmisch oft laufen, nicht die falschen Folgerung des TEs </nitpick>
@kolwe96 Versuch einmal, den Graph des Produktes der Funktionen und deiner berechneten Komplexitätsfunktion zu vergleichen. Fällt dir etwas auf? Könnte ich vielleicht in der Lage sein, für jeden beliebigen Quotient zwischen dem Produkt und deiner Funktion () einen Parameter n zu finden sodass dieser Quotient erreicht wird? Was sagt das über die Korrektheit deiner Komplexitätsfunktion aus?
-
@Columbo sagte in Komplexität:
Was O(n)O(n)O(n) entspricht.
Ja. Die Folgerung O(n)*O(log(n))*O(log(n))==O(n)? ist trotzdem Quatsch.
-
@Swordfish Sorry, ich sehe erst jetzt dass meine Antwort irreführend ist
-
@Columbo NP. OP muss es eh selbst lernen. Du darfst gern nach dem picken die hälfte deiner nits abgeben ... ich hab auch hunger!
-
Ich nutze zum Überwachen meiner Projekte den SourceMonitor.
http://www.campwoodsw.com/sourcemonitor.htmlDamit kann man auch die Komplexität der Methoden im Blick behalten, aber eben auch viele andere Parameter des aktuellen Projekts. ( diese Komplexität ist gemeint: https://de.wikipedia.org/wiki/McCabe-Metrik )
Edit: du brauchst vermutlich eine andere Komplexität, als diejenige, die das Tool berechnet.
-
@It0101 sagte in Komplexität:
Ich nutze zum Überwachen meiner Projekte den SourceMonitor.
http://www.campwoodsw.com/sourcemonitor.htmlSieht gut aus. Werde ich mal ausprobieren.
Ich habe sonst das hier benutzt: https://scitools.com/
Ideal auch, um sich durch fremden Code zu wühlen.
-
Wenn ich den SourceMonitor auf den geleakten Code von Win2K loslasse, hängt er sich erst mal auf (Eieruhr und reagiert nicht mehr auf Mouse-Clicks). Naja, ist wohl zu viel für ihn. Ich gebe ihm noch etwas Zeit.
-
@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.