以下嵌套循環的時間複雜度是多少？

for i=1 to n 
    for j=1 to i 
     for k=1 to j 
      x+=1

for i=1 to n 
    for j=1 to i 
     for k=1 to i 
      x+=1

我也覺得這一個是N 因爲內部循環仍依賴於最外層循環。

請驗證我的回答，並解釋我爲什麼錯了。

這是一個說明性的圖n與你的算法的運行時間的各種n值（但包括一個固定的持續時間睡眠/暫停在x + = 1步，以便您可以使用n的合理值）。查看圖形的形狀以獲得關於複雜性的最初概念。 –

或者只是繪製x的值，因爲它只能增加1。但是，sum（1..n）是n *（n + 1）/ 2，它在O（n^2）複雜等級中，如n * n。因此，在外環循環計數器上線性依賴的循環邊界不會改變事物。 –

在實踐中，它通常要快得多，而且如果通常會發生早期失敗，那麼它可能非常重要。（例如，考慮在字符串中查找重複的字符，檢查整個字符串以重複當前的字符，而不是檢查前面的元素。對於沒有重複第一個字符的巨大字符串，它是巨大的。）因爲你必須分別考慮這種情況，或者說明早期採取的頻率。 –

假設你有第一個正確的。那麼你可以很容易認爲第二個版本的複雜性至少是第一個版本的複雜性。爲什麼？版本之間的唯一區別是第二個版本有k = 1 to i，第一個版本有k = 1 to j。但在第一個版本中，j總是小於或等於i。所以在第二個版本中，k的循環將會經常運行得更頻繁。

現在考慮這段代碼：

for i=1 to n 
    for j=1 to n 
     for k=1 to n 
      x+=1

首先，表明這個時間複雜度爲爲O（n ）。然後，進行一個類似於我上面所做的論證，以顯示此代碼的複雜性大於或等於您的第二個版本的複雜性。得出這樣的結論所有三個代碼段的複雜性必須是爲O（n 3 ）如果所述第一個的複雜度，然後顯示所述第一的複雜度是爲O（n 3 ）。

2015-09-24 02:27:02 Patrick87

回答