Was ist die Komplexität dieses Codes, dessen verschachtelte for-Schleife seinen Zähler wiederholt verdoppelt?

8

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%     
Nick Chris 05.09.2012, 17:19
quelle

3 Antworten

15

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

%Vor%

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.

%Vor%

Nun, Stirlings Formel sagt uns

%Vor%

Wir finden also die gesamte geleistete Arbeit in der Tat O(N) .

    
Daniel Fischer 05.09.2012, 18:55
quelle
4

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%     
Tony Tannous 09.08.2017 14:22
quelle
1

@Daniel Fischers Antwort ist richtig.

Ich möchte hinzufügen, dass die genaue Laufzeit dieses Algorithmus wie folgt ist:

Was bedeutet:

    
quelle