這段代碼片段的複雜程度如何？

我有一個關於下面的代碼的時間複雜性的問題。我猜測時間複雜度是，但我的朋友告訴我時間複雜度應該是O（n^2）。但是，我仍然不相信答案。我的立場是：第一個和第二個循環會花費O（1/2 n^2），內循環需要另外一些O（n）複雜度。因此，這是關於O（n^3）。這段代碼片段的複雜程度如何？

for (int i = 1; i <= len; i++) { 
    for (int j = i + 1; j <= len; j++) { 
     int mid = (i + j)/2; 
     for (int k = i; k <= j; k++) { 
      dist[i][j] += Math.abs(A[k - 1] - A[mid - 1]); 
     } 
    } 
}

來源

2016-04-17 blackhazelnut

什麼是你的朋友的背後N^2 –

注意，O（N²）⊂O（N 3）推理，所以你可以既正確。 –

他說第二個循環是i + 1，所以第二個循環會循環O（1/2n^2）次，但他沒有考慮到最後一個循環。 – blackhazelnut

所以，你需要找到的東西的時間複雜度是這樣的：

for (int i = 1; i <= N; i++) { 
    for (int j = i + 1; j <= N; j++) { 
     for (int k = i; k <= j; k++) { 
      // some O(1) operation 
     } 
    } 
}

在每一個O（N）運行循環，所以複雜度爲O（N^3）。你也可以寫在你的語言簡單的測試程序（我在python寫）：

def check(N): 
    s = 0 
    for i in xrange(1, N + 1): 
     for j in xrange(i + 1, N + 1): 
      for k in xrange(i, j + 1): 
       s += 1 
    return s 

print [check(i) for i in xrange(1, 10)] // [0, 2, 7, 16, 30, 50, 77, 112, 156]

，並檢查了closed form for this sequence。這是，

這顯然是爲O（n^3）

來源

2016-04-17 02:51:17

這段代碼片段的複雜程度如何？

回答

相關問題