基本算法的書，澄清需要

Integer: FindMedian(Integer: array[]) 
For i = 0 To array.Length - 1 
// Find the number of values greater than and less than array[i]. 

Integer: num_larger = 0 
Integer: num_smaller = 0 

For j = 0 To array.Length - 1 
    If (array[j] < array[i]) 
     Then num_smaller = num_smaller + 1 
    If (array[j] > array[i]) 
     Then num_larger = num_larger + 1 Next j 
    If (num_smaller = num_larger) 
     Then Return array[i] 
    End If 
Next i 
End FindMedian

現在有關的algoritm的複雜性，作者說：基本算法的書，澄清需要

如果數組包含N個值，外因爲我循環執行N次。對於這些迭代中的每一個，內部For For循環執行N次。這意味着內循環內部的步驟執行N×N = N次，給算法運行時間O（N）。

我認爲複雜度應該是O（N^2）。我錯了嗎？

來源

2015-06-24 Rajat Saxena

你可以在代碼中放置一些換行符嗎？它看起來像一條線。 –

當然，我已經在上面了。我張貼使用SO安卓應用程序，它做了所有的混亂。 –

現在它應該縮進4個字符。 –

當然訂單將是o（N^2），因爲對於每個外部循環你的內部循環將運行n次所以有n個外部循環。時間複雜度將爲o（n^2）。

請問您可以與您分享的書頁鏈接找到它的頁碼？

來源

2015-06-24 04:20:07

書的名字在帖子的標題和第3章（數組） –

如果數組包含N個值，則外部For i循環執行N次。對於每一次迭代，Inner For j循環執行N次。這意味着內循環內部的步驟執行N×N = N2次，給算法運行時間O（N2）。這些行完全從書中複製。書是正確的，但有打印錯誤。 –

是的，我認爲是。

從https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

O(N^2)表示一種算法，其性能是直接正比於輸入數據集的大小的平方。這在涉及數據集的嵌套迭代的算法中很常見。更深層次的嵌套迭代將導致O(N^3)，O(N^4)等

bool ContainsDuplicates(IList<string> elements) 
{ 
    for (var outer = 0; outer < elements.Count; outer++) 
    { 
     for (var inner = 0; inner < elements.Count; inner++) 
     { 
      // Don't compare with self 
      if (outer == inner) continue; 

      if (elements[outer] == elements[inner]) return true; 
     } 
    } 

    return false; 
}

哪個是你問什麼。

來源

2015-06-24 04:09:44

那麼這意味着作者是錯的？ –

基本算法的書，澄清需要

回答

相關問題