Wie kann ich die zeitliche Komplexität dieses Algorithmus analysieren?

Question

Was wird die Zeitkomplexität für verschachtelte Schleifen

for (i=1; i<=n; i++) { 
    for (j=1; j<=log(i); j++) { 
     O(1); 
    } 
} 

, wo n durch den Benutzer gegeben ist? Ist die zeitliche Komplexität nur von den Loop-Variablen oder der bedingten <= abhängig?

Answer 1

Die Zeitkomplexität ist normalerweise unabhängig von Benutzereingaben (in diesem Fall: n). Die erste Schleife führt n Iterationen durch und die zweite Schleife führt im schlimmsten Fall Log (n) Iterationen durch. Da Sie den Schleifenkörper nicht bereitgestellt haben, vorausgesetzt, dass die Operationen in der Schleife O (1) sind, ist die Komplexität O (n log n).

In Bezug auf Ihre zweite Frage hängt es sowohl von Ihrer Schleife und "Vergleichsteil" (Schleifenkörper).

Answer 2

Die Zeit Komplexität hängt von allem ab, was Zeit braucht, also ja, es hängt von den Grenzen der for Schleife ab. Es funktioniert im Allgemeinen am besten, um Schleifen von innen heraus zu analysieren. Also

for (j=1; j<=log(i); j++) { 
     O(1); 
    } 

dauert O(1)*log(i)=O(log(i)) Zeit. Dann können wir die ganze Schleife schreiben als

for (i=1; i<=n; i++) { 
    O(log(i)); 
} 

Die einfachste Sache an diesem Punkt ist, einfach alles zu addieren. Die Gesamtzeit ist daher:

O(log(1))+O(log(2))+O(log(3))+...+O(log(n-2))+O(log(n-1))+O(log(n)) 
=O(log(1) + log(2) + log(3) +...+ log(n-2) + log(n-1) + log(n)) 

Aufgrund der Eigenschaften von Logarithmen, dann ist dies O(log(n!)) und durch Stirling’s approximation, ist dies O(n log(n)).