Was wäre die zeitliche Komplexität und warum?

Question

Was wäre die Zeit Komplexität der Methode unten und warum?

Ich weiß, dass es wegen der ersten for-Schleife größer als O (n) sein muss.

Aber was passiert mit der Zeit Komplexität nach der While-Schleife?

Ist es O (n) (n-1) = O (n^2 + n)?

int fnA(int n) { 
    int sum=0; 
    for (int i=0; i<n; i++) { 
     int j=i; 
     int product =1; 
     while (j>1) { 
      product ∗= j ; 
      j = j/2; 
     } 
     sum += product; 
    } 
    return sum; 
} 

Answer 1

Das sieht für mich wie O(n log n) aus. Die Hauptschleife iteriert n mal, und jede Iteration benötigt log n zusätzliche Iterationen, um abzuschließen, seit j beginnt bei i und ist halbiert bis j <= 1. Wenn Sie sich die Gesamtzeit für alle Iterationen der inneren Schleife vorstellen, erhalten Sie die folgende Summe.

O(0 log n) + O(1 log(n-1)) + ... + O(n/2 log (n/2)) + ... + O((n-2) log 2) + O((n-1) log 1) = 
O(log n) + O(n log n) + O(n) = 
O(n log n)