爲什麼CompareToAll最快的運行時間是O（1）？

in實現使用CompareToAll methodolgy獲取數組中的最大數量，增強不會將每個數字與每個其他數字進行比較，但會將每個數字與僅出現在其後面的數字進行比較。實質上，當前數字之前的每個數字已經與當前數字進行了比較。因此，如果僅比較當前數字之後出現的數字，算法仍然正確。現在我明白爲什麼最壞的情況下運行時間是O（n2）O（「n square」）但我不明白的是爲什麼最快的運行時間是O（1）。爲什麼CompareToAll最快的運行時間是O（1）？

我想這應該是在最好的情況下等於O（n）的 Big-O analysis for best case is copied from

來源

2011-02-27 Ali Abdel-Aziz

的Max()功能的最小複雜性O(n)，不O(1)，因爲你必須在每個數字看起來至少一次。

您只需要將每個數字與前一個最大值進行比較。這是在Python代碼：

def max(a): 
    assert len(a) > 0 
    current = a[0] 
    for x in a[1:]: 
     if x > current: current = x 
    return current

來源

2011-02-27 18:54:02 Apalala

對於一個有序數組，最快的時間爲O（1），因爲你可以簡單地選擇第一個或最後一個元素，根據不同的排序方向。但是，對於非排序的數組，我無法預見任何可以在小於O（n）時間內找到最大值的算法。

爲什麼：假設我們有一個包含n個沒有已知順序的元素的數組。選擇第一個元素;這可能是最大的。但是，你怎麼知道第二個元素不是最大值？你必須測試它。同樣，你怎麼知道第三個元素不是最大值？依此類推，進行n次測試。

來源

2011-02-27 18:57:11 erisco

爲什麼CompareToAll最快的運行時間是O（1）？

回答

相關問題