這個函數的大O符號是什麼？

我知道大O符號是衡量一個函數效率的一個度量，但我真的不知道如何計算它。這個函數的大O符號是什麼？

def method(n) 
    sum = 0 
    for i in range(85) 
     sum += i * n 
    return sum

答案是否是O（f（85））？

來源

2013-12-11 kiasy

這裏的運行時間似乎是不變的（即不變的'n'）... –

你有4個「動作」功能，來計算其大O上，我們需要計算大O字的每一個動作，然後選擇最高：

總和= 0 - 固定的時間，測量O（1）
我在範圍（85） - 恆定時間，85次迭代，O（1 *複雜度爲＃3）
sum + = i * n - 我們可以說恆定時間，但乘法實際上取決於位長度我和n，所以我們可以說O（1）或者O（max（lenI，lenN））
return sum - constant time，measured O（1）

因此，只要lenI和lenN是常數（通常爲32或64位），max（lenI，lenN）就是可能的最大大O是＃2，即1 * O（＃3） - > 32/64，所以你的函數的總複雜度是O（1 * 1）= O（1）

如果我們有大的數學，即N的位長度可以非常長，那麼我們可以說O（位長N）

注：位長N實際上是LOG2（N）

來源

2013-12-11 20:19:25

...更新了我的答案，O（log2 n）等於O（log n）。 – pepr

@pepr在數學世界中最好提到日誌庫，因爲只是日誌通常意味着log10，而在計算機世界中日誌通常意味着log2。所以我更喜歡在這裏指出基地（當然，您可以通過const從log2轉換爲log10，然後只需寫入無日誌的日誌） –

我知道你知道。 :)而且任何常量都不會改變O（）。 – pepr

的此功能的複雜性是在RAM模型發生在固定時間內基本的數學函數O（1）

。在此函數中的主導術語是

for i in range(85):

因爲85是一個恆定的複雜度爲O（1）表示

來源

2013-12-11 20:12:52 robbmj

你能解釋爲什麼嗎？ – kiasy

我用解釋 – robbmj

在理論上，複雜度爲O（log n）的。隨着n增長，讀取數字並執行乘法需要更長的時間。

但是，在實踐中，n的值受到限制（有一個最大值），因此可以在O（1）時間內讀取並執行操作。由於我們重複O（1）操作一定的時間，所以複雜度仍然是O（1）。請注意，O（1）表示常量時間 - O（85）並不意味着任何不同。如果在一個序列中執行多個常量時間操作，則除非序列的長度取決於輸入的大小，否則結果仍爲O（1）。執行O（1）操作1000次仍然是O(1)，但這樣做n次是O(n)。

如果你想真的玩起來安全，就說O(∞)，那絕對是一個正確的答案。然而，CS教師在實踐中往往不會真正欣賞它。

來源

2013-12-11 20:19:21 kviiri

當談到複雜性時，總是應該說什麼操作應該被視爲恆定時間（最初的協議）。這裏可以考慮整數乘法或者是不變的。無論如何，這個例子的時間複雜度比O（n）好。但這是老師對學生的詭計 - 有點兒。 :)

來源

2013-12-11 20:57:37 pepr

這個函數的大O符號是什麼？

回答

相關問題