運行代碼片段

Question

這裏的時間複雜度是所述片段：

sum1=0; 
    for(i=1;i<=n;i++) 
     for(j=1;j<=n;j++) 
     sum1++ 
sum2=0 
    for(k=1;k<=n;k*=2) 
     for(j=1;j<=k;j++) 
     sum2++ 

下面是答案：

2賦值語句 - O（1）各 第一嵌套循環 - O（N2） 第二個嵌套循環 - O（n） 運行時代碼複雜度= O（1）+ O（n^2）+ O（1）+ O（n）= O（n2）

但是，我解決了它：

2作業： - O（1）。 第一個嵌套循環：O（N * N）= O（N^2） 第二嵌套循環：

外部循環運行N次.. 現在內部循環將被執行（1 + 2 + 3 +。 ... +（n-1）+ n）乘以 其給出n（n + 1）/ 2 = 0（n^2）

總運行時間= O（n^2）+ O（n^2）+ O（1）= O（N^2）

是的，我已經做了一些研究，我碰到下面傳來：

在一個循環，如果一個指數的增加量跳躍每次迭代該序列具有複雜度l og n。

在這種情況下，我假設第二個循環將具有等於O（n * log n）的複雜度（n-1）/ 2 * logn ...。

我與第二循環是否應該爲O（n）..爲O（n^2）或O（nlogn）真糊塗..

幫助請

Answer 1

既然你ķ增加每次加倍。你的計算不正確。它應該是（1 + 2 + 4 + .... n/2 + n）

 for(k=1;k<=n;k*=2) 

所以，O（nlogn）是正確的。