これの時間の複雑さとその理由は何でしょうか？

Question

以下の方法の時間的複雑さとその理由は何ですか？

最初のforループのため、O（n）より大きい必要があります。

しかし、whileループ後の時間の複雑さはどうなりますか？

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

これは私にO(n log n)のように見えます。メインループはn回反復し、jがiで始まり、j <= 1まで半分になるので、各反復は完了するためにlog nの追加の反復を必要とします。内側ループのすべての反復の合計時間を想像すると、次の合計が得られます。

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)