Wie lautet die Laufzeit des Codeausschnitts?

Question

Kann mir jemand helfen, die Laufzeitkomplexität des folgenden Codeausschnitts zu finden?

bitte helfen Sie mir bei der Suche nach der Laufzeit Komplexität des oben genannten Code-Snippet.

Answer 1

Ich denke, Ihr Code hat ein Problem, vor allem in der ersten While-Schleife.

while (i <= n); 

ein Semikolon nach while loop Anweisung mit Mitteln, gibt es keine Erklärung unter der Schleifenanweisung. Zu Ihrer Information wird diese while-Schleife unendlich ausgeführt, weil Sie die Schleifenvariable i nicht aktualisieren.

Falls Sie versehentlich das Semikolon gesetzt haben, dann wird die while n mal durchlaufen, was die Zeit Komplexität für diese while-Schleife als O(n) macht.

Aber die Zeit Komplexität Ihrer zweiten While-Schleife ist O(log n), weil Sie die Loop-Variable j durch Halbieren des Werts verringern.

while (j > 0) 
    y := x/(2*j); 
    j = j /2; 
    i = 2 *i; 

insgesamt Also, wenn man bedenkt, sowohl die While-Schleifen, dann sollte die Gesamtzeit Komplexität O(n + log n) sein, die zu O(n) entspricht.