算法的時間複雜性是否正常？

Question

我想設計一個時間複雜度爲O(n(log(2)n)^2)的算法。我寫了這個：

for(int i=1; i<=n; i++){ 
j=i; 
while(j != 1) 
    j=j/2; 

j=i; 
while(j !=1) 
    j=j/2; 
} 

它有O（n（log（2）n）^ 2）時間複雜度嗎？如果沒有，我哪裏出錯了，我該如何解決它，使其時間複雜度爲O(n(log(2)n)^2)？

Answer 1

輕微的題外話：

正如你們說的意見，算法確實O(n log n)。這恰好與通過將內部環路的複雜性乘以外部環路（即O(log i) x O(n)）所獲得的結果相同。

這可能會導致你相信，我們可以簡單地添加內部循環的另一次迭代獲得(log n) 部分：

for (int i = 1; i < n; i++) { 
    int k = i; 
    while (k >= 1) 
     k /= 2; 
     int j = i; 
     while (j >= 1) 
      j /= 2; 
    } 
} 

但讓我們來看看原來的複雜性是如何得出：

（使用英鎊的近似值）

因此，擬議的修改將使：

這是不是我們想要的。

---

我可以從最近的個人項目想到的一個例子是半幼稚KD樹建設。的僞代碼在下面給出：因此

def kd_recursive_cons (list_points): 
    if length(list_points) < predefined_threshold: 
     return new leaf(list_points) 

    A <- random axis (X, Y, Z) 
    sort list_points by their A-coordinate 

    mid <- find middle element in list_points 
    list_L, list_R <- split list_points at mid 

    node_L <- kd_recursive_cons(list_L) 
    node_R <- kd_recursive_cons(list_R) 

    return new node (node_L, node_R) 
end 

的時間複雜度函數由下式給出：

凡n log n部分是從排序。我們顯然可以忽略線性部分Dn，也可以忽略常數C。因此：

這正是我們想要的。

---

現在寫一個簡單的代碼片段，具有相同的時間複雜度。我們可以利用我們在上述推導中獲得的總和...

，並指出，傳遞給log函數的參數是由兩個在每個循環劃分，我們可以這樣寫代碼：

for (int i = 1; i < n; i++) { 
    for (int k = n; k >= 1; k /= 2) { 
     int j = k; 
     while (j >= 1) 
      j /= 2; 
    } 
} 

這看起來像「幼稚」，但不正確解決方案在開始時提到，區別在於那裏的嵌套循環有不同的邊界（j不取決於k，但k取決於i而不是直接在n）。

---

編輯：一些數值試驗，以確認的複雜性爲目的：

測試功能代碼：

int T(int n) { 
    int o = 0; 
    for (int i = 1; i < n; i++) 
     for (int j = n; j >= 1; j /= 2) 
      for (int k = j; k >= 1; k /= 2, o++); 
    return o; 
} 

數值結果：

n   T(n) 
------------------- 
2   3 
4   18 
8   70 
16   225 
32   651 
64   1764 
128   4572 
256   11475 
512   28105 
1024  67518 
2048  159666 
4096  372645 
8192  860055 
16384  1965960 
32768  4456312 
65536  10026855 
131072  22413141 
262144  49807170 
524288  110100270 

然後我繪製sqrt(T(n)/n)反對n。如果複雜性是正確的，那麼應該給出log(n)圖或者如果以對數座標水平軸作圖，則可以得到直線。

而且這確實是我們得到：