Wie finden Sie die asymptotische Zeitkomplexität dieser Schleifen?

Question

Wie finden Sie die asymptotische Zeitkomplexität dieses Codes?

In meinen Notizen habe ich die Antwort O (n * log (logn)) aber ohne eine Erklärung.

Answer 1

Die erste for-Schleife läuft n-mal. Die innere Schleife iteriert in Quadraten und benötigt daher O(loglogn). Somit ist die Gesamtkomplexität O(n*log(logn)).

Um zu verstehen, warum das Iterieren in Quadrate O(log(logn)) Zeit in Anspruch nehmen, sehen so aus:

Es sei n die große Zahl als 2^16.

Initially: j = 2 
1st step : j = 2^2 
2nd step : j = 2^4 
3rd step : j = 2^8 
4th step : j = 2^16. 

Daher dauert es nur 4 Schritte, die Loglog (2^16) ist.

So jetzt für jede n = 2^k, Sie beginnen mit 2 und jedes Mal, wenn Sie sich quadrieren. Also, es kann am meisten O(logk) quadrieren können Sie tun, um k zu erreichen. Seit n = 2^k, So, k = log(n) und damit O(logk) ist das gleiche wie O(log(logn)).