Ich studiere gerade und versuche, einige Algorithmen zu implementieren. Ich versuche, Big O-Notation zu verstehen, und ich kann nicht die Big O Komplexität für den Algorithmus herauszufinden unten:Big O Notation und Algorithmen
while (a != 0 && b != 0)
{
if (a > b)
a %= b;
else
b %= a;
}
if (a == 0)
common=b;
else
common=a;
Es ist leicht zu sehen, dass nach zwei Iterationen die kleinste der Zahlen mindestens zweimal kleiner wird. Wenn es am Anfang gleich m war, wird es nach 2K Iterationen nicht mehr als m/2^K sein. Wenn wir hier K = [log_2 (m)] + 1 setzen, sehen wir, dass nach 2K-Iterationen die kleinste der Zahlen Null wird und die Schleife endet. Daher ist die Anzahl der Iterationen nicht mehr als 2 (log_2 m + 1) = O (log m).
Die meisten Menschen (die nicht Mathematiker) nie das Zeug, um herauszufinden, benötigen, ist es bereits dokumentiert: http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency
Antwortet nicht auf die Frage (was ist die Big-O-Notation für den gegebenen Algorithmus) (-1) –
Es beantwortet die Frage. "Euclids Algorithmus wächst quadratisch (h2) mit der durchschnittlichen Anzahl von Ziffern h in den ersten zwei Zahlen a und b." -> O (h^2) – fejesjoco
Außer wenn ich dies ohne Kontext antworte, würde er es nicht verstehen. Ich werde auch nicht den ganzen Beweis zeigen. Ich glaube also, dass der Wikipedia-Artikel die bestmögliche Antwort war. – fejesjoco
Das ist der euklidische Algorithmus zur Berechnung des größten gemeinsamen Teilers von zwei ganzen Zahlen. Ich überlasse es Ihnen, die Komplexität dieses Algorithmus zu untersuchen, aber die Fibonnacci-Zahlen spielen eine wichtige Rolle.
Es wäre schön, wenn Sie auch ein Beispiel für Zahlen hinzufügen könnten, die 'O (log m)' Schritte benötigen, um zu zeigen, dass diese Grenze eng ist. – liori
können Sie Kommentare zum obigen Code hinzufügen? So können Sie angeben, wie Sie zu dieser Schlussfolgerung kommen können? –
@tristan Sie meinen, warum das Minimum der Zahlen auf diese Weise abnimmt? Angenommen a> b, dann ist nach einer Iteration das Minimum c = a% b, und nach 2 Iterationen ist es b% c. Wenn c <= b/2, dann ist b% c b/2, dann ist b% c = b-c
adamax