Ich studiere die Komplexität des Algorithmus und bin immer noch nicht in der Lage, die Komplexität einiger Algorithmen zu bestimmen ... Ok, ich bin in der Lage, grundlegende O (N) und O (N^2) Schleifen zu finden, aber ich bin etwas schwierig in Routinen, die wie diese:Wie berechnet man effektiv die zeitliche Komplexität eines Algorithmus?
// What is time complexity of fun()? int fun(int n) { int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count; }
Ok ich weiß, dass einige Leute diese geschlossen mit den Augen berechnen kann aber ich würde einen „Schritt“ durch „Schritt“, um zu sehen, lieben, wie man wenn möglich.
Mein erster Versuch zur Lösung dieses wäre zu „simulieren“ einen Eingang und stellen Sie die Werte in einer Art Tabelle, wie unten:
for n = 100 Step i 1 100 2 50 3 25 4 12 5 6 6 3 7 1
Ok ich an dieser Stelle, dass dies unter der Annahme, bin Schleife ist O (logn), aber leider, wie ich sagte, niemand löst dieses Problem "Schritt" durch "Schritt", so am Ende habe ich keine Ahnung, was alles getan wurde ....
Im Falle der innere Schleife Ich kann eine Art Tabelle wie folgt erstellen:
for n = 100 Step i j 1 100 0..99 2 50 0..49 3 25 0..24 4 12 0..11 5 6 0..5 6 3 0..2 7 1 0..0
Ich kann sehen, dass beide Schleifen abnehmen und ich nehme an kann eine Formel oben ... klären dieses Problem
Könnte jemand basiert auf Daten abgeleitet werden? (Die Antwort ist O (n))
Simulieren kann Ihnen Intuition geben, aber der einzige Weg, eine definitive Antwort zu erhalten, ist, sie analytisch abzuleiten. –
Ja, ich verstehe ... aber wie kann ich Schritt für Schritt wissen, dass dieser Algorithmus O (n) ist? – marcoshass
Sie haben bereits die Anzahl der Operationen gezählt. Es ist n + n/2 + n/4 + ... + 1. 'n + n/2 + n/4 + ... + 1 '<=' n * SUM (1/2^k), für k = [0, inf) '<=' n * 2' ∈ 'O (n)' – DAle