Was ist die Komplexität dieses Codes, dessen verschachtelte for-Schleife seinen Zähler wiederholt verdoppelt?
In dem Buch Programming Interviews Exposed heißt es, dass die Komplexität des unten stehenden Programms O (N) ist, aber ich verstehe nicht, wie das möglich ist. Kann jemand erklären, warum das so ist?
%Vor%3 Antworten
Du brauchst ein bisschen Mathematik, um das zu sehen. Die innere Schleife iteriert Θ(1 + log [N/(i+1)]) mal (die 1 + ist notwendig, da für i >= N/2 , [N/(i+1)] = 1 und der Logarithmus 0 ist, aber die Schleife iteriert einmal). j verwendet die Werte (i+1)*2^k , bis es mindestens so groß ist wie N und
mit mathematischen Division. Das Update j *= 2 heißt also ceiling(log_2 (N/(i+1))) mal und die Bedingung wird 1 + ceiling(log_2 (N/(i+1))) mal geprüft. So können wir die Gesamtarbeit schreiben.
Nun, Stirlings Formel sagt uns
%Vor% Wir finden also die gesamte geleistete Arbeit in der Tat O(N) .
Die äußere Schleife läuft n mal. Jetzt hängt alles von der inneren Schleife ab
Die innere Schleife ist jetzt die knifflige.
Lässt folgen:
%Vor% %Vor%@Daniel Fischers Antwort ist richtig.
Ich möchte hinzufügen, dass die genaue Laufzeit dieses Algorithmus wie folgt ist:
Was bedeutet:
Tags und Links algorithm time-complexity complexity-theory big-o