我的函數在O（n）中運行嗎？

我有一個函數來查找排序數組s中是否有數字，這些數字加起來就是給定的總和x。我想知道這個功能的大喔複雜性是什麼。我認爲它運行在O（n），但我不確定。我的函數在O（n）中運行嗎？

功能：

def sumInside(s, x): 
    # Two indices that will be compared 
    l = 0 
    r = len(s) - 1 

    # Go through the array for the elements 
    while l < r: 
     if s[l] + s[r] == x: 
      return True 
     elif s[l] + s[r] < x: 
      l += 1 
     else: 
      r -= 1 
    return False

來源

2017-10-08 tushariyer

兩個規則：

多少次迭代在你的數據嗎？
每次迭代會發生什麼？

對第一個問題的回答是n。你有一個循環，它遍歷整個數據一次。

第二個問題也很容易回答。您可以在每個循環中進行比較，這是一個恆定的時間操作。

總體而言，您的功能在最差情況下以線性時間運行 - O(n)。

來源

2017-10-08 20:26:23

謝謝！我會遵守規則 – tushariyer

在(O(n))的O意味着採取最壞的情況下的時間。如果我們將比較作爲基本操作，對於n元素輸入大小，在最壞的情況下會有2 * n比較。所以這個例子有一個線性處理時間（O（n））的拇指

來源

2017-10-08 20:26:02 thoron

「大哦意味着最壞的情況下」不，不。你可以使用big-oh來推理你想要的任何情況（或甚至關於最佳或最壞情況的概念甚至沒有意義的功能/屬性）。 – sepp2k

確實。大哦，只是簡單地指定了一個函數的漸近上界，並沒有提到函數的最壞/最好/平均/甚至分期複雜化。 –

是，O(n)最壞的情況

最壞的情況下，你的元素是最右邊（L必須增加一路向右），這將是n倍。

如果是在最左邊的O(1)，您可以在第一次嘗試中找到它。當時l = 0。

從理論上講，平均情況x總是在中間，這將需要n/2次迭代，即O(n)。

最佳：O(1)
均價：O(n)
最差：O(n)

來源

2017-10-08 20:26:57

我的函數在O（n）中運行嗎？

回答

相關問題