Komplexität

[kolwe96]

Hi, kann mir jemand erklären wie ich die Komplexität von dem folgenden Algorithmus bestimme?

for(int i=n ; i>0 ; i/=2){
for(int j=1 ; j<n ; j*=2){
for(int k=0 ; k<n ; k+=2){
//konsanter Anteil
}
}
}

Danke schonmal

[Columbo]

Wie waere es, wenn Du die Zahl der Schleifendurchläufe als Funktion von n bestimmst?

[kolwe96]

Ich habe dazu leider keinen Ansatz...

[Swordfish]

anzahl_durchläufe_von_for_1 * anzahl_durchläufe_von_for_2 * anzahl_durchläufe_von_for_3 in abhängigkeit von n.

[kolwe96]

Also O(n)*O(log(n))*O(log(n))==O(n)?

[Th69]

This post is deleted!

[Swordfish]

ä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).

[Columbo]

@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 $O(n)$ 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 ($n$) einen Parameter n zu finden sodass dieser Quotient erreicht wird? Was sagt das über die Korrektheit deiner Komplexitätsfunktion aus?

[Swordfish]

@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.

[Columbo]

@Swordfish Sorry, ich sehe erst jetzt dass meine Antwort irreführend ist

[Swordfish]

@Columbo NP. OP muss es eh selbst lernen. Du darfst gern nach dem picken die hälfte deiner nits abgeben ... ich hab auch hunger!

[It0101]

Ich nutze zum Überwachen meiner Projekte den SourceMonitor.
http://www.campwoodsw.com/sourcemonitor.html

Damit 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.

[RBS2]

@It0101 sagte in Komplexität:

Ich nutze zum Überwachen meiner Projekte den SourceMonitor.
http://www.campwoodsw.com/sourcemonitor.html

Sieht 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.

[RBS2]

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.

[It0101]

@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.

[RBS2]

@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.

[Mechanics]

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.

[EinNutzer0]

@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)

[RBS2]

This post is deleted!

[Th69]

@EinNutzer0 sagte in Komplexität:

also ist die Komplexität n log(n)

Nein, die Schlußfolgerung ist falsch.
Es ist n * log(n) * log(n), also kurz n * log²(n).