0

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

+0

Simulieren kann Ihnen Intuition geben, aber der einzige Weg, eine definitive Antwort zu erhalten, ist, sie analytisch abzuleiten. –

+0

Ja, ich verstehe ... aber wie kann ich Schritt für Schritt wissen, dass dieser Algorithmus O (n) ist? – marcoshass

+1

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

Antwort

1

Eine weitere einfache Möglichkeit wahrscheinlich um es zu betrachten ist:

Ihre äußeree Schleife i initialisiert (Schritt/Iterator betrachtet werden kann) bei n und teilt i nach jeder Iteration von 2. Daher führt es die i/2-Anweisung log2 (n) mal aus. Also, eine Möglichkeit, darüber nachzudenken ist, Ihre äußere Schleife log2 (n) mal laufen. Wenn Sie eine Zahl fortlaufend durch eine Basis teilen, bis sie 0 erreicht, führen Sie das Divisionsprotokoll tatsächlich mehrmals durch.Daher ist die äußere Schleife O (log-base-2n)

Ihre innere Schleife iteriert j (jetzt der Iterator oder der Schritt) von 0 bis i bei jeder Iteration der äußeren Schleife. Ich nehme den Maximalwert von n, daher wird der längste Lauf, den Ihre innere Schleife haben wird, von 0 bis n sein. Also ist es O (n).

nun Ihr Programm läuft wie folgt aus:

Run 1: i = n, j = 0->n 
Run 2: i = n/2, j = 0->n/2 
Run 3: i = n/4, j = 0->n/4 
. 
. 
. 
Run x: i = n/(2^(x-1)), j = 0->[n/(2^(x-1))] 

nun Zeit runnning immer "Multiplikationen" für verschachtelte Schleifen, so O (log-base-2 n) * O (n) gibt O (n) für Ihren gesamten Code

1

Lässt diese Analyse in ein paar Schritten brechen.

Zuerst beginnen mit der inneren for-Schleife. Es ist einfach zu sehen, dass dies genau i Schritte dauert.

Als nächstes überlegen, welche verschiedenen Werte i im Laufe des Algorithmus annehmen wird. Zu Beginn betrachte man den Fall, in dem n eine Potenz von 2 ist. In diesem Fall beginnt i bei n, dann n/2, dann n/4 usw., bis es 1 und schließlich 0 erreicht und schließlich endet. Da die innere Schleife jedes Mal i Schritte benötigt, ist die Gesamtzahl der Schritte fun(n) in diesem Fall genau n + n/2 + n/4 + ... + 1 = 2n - 1.

Zuletzt, Überzeugen Sie sich selbst dies verallgemeinert zu Nicht-Befugnisse von 2. Bei einem Eingang n, finde die kleinste Potenz von 2 größer als n und nenne es m. Klar, n < m < 2n, so fun(n) dauert weniger als 2m - 1 Schritte, die weniger als 4n - 1 ist. Somit ist fun(n)O(n).

Verwandte Themen