代碼的時間複雜度是多少？

下面的代碼O（NV^2）的時間複雜度是多少？代碼的時間複雜度是多少？

for i from 1 to N: 
    for j from 1 to V: 
     for k from 1 to A[i]://max(A) = V 
      z = z + k

2014-09-13 象嘉道

這就像你說的。唯一的例外可能是，如果A [i]，儘管最大可能是V，它將例如總是「平均」（攤銷複雜度）。不會更詳細 - 有很多很好的資源。當然，還有大學。 – PawelP 2014-09-13 15:54:24

對於Pawell所說的一個例子，假設除了一個單獨的值（即V）外，A是滿零的。內部循環將只運行於那個i，因此總的時間複雜度爲O（NV + V^2 ） – hugomg 2014-09-13 16:28:44

是的，時間複雜度是O（NV^2）。就這些。 – Hungry 2014-09-13 17:55:14

是的，每當我們談論O-notation，我們經常思考上限（或最壞情況）。

因此，該代碼的複雜性將等於

O(N*V*maximum_value_of_A) 
=O(N*V*V) // since,maximum value of A=V,so third loop can maximally iterate from 1 to V---V times 
=O(N*V^2).

2014-09-13 15:51:26

也請提出答案！ – 2014-09-14 19:28:26

對於

確保它是O（NV^2），因爲它意味着該代碼是從不低於慢。由於max（A）= V，可以說最壞的情況是在A的每個索引處有V時。如果是這樣，那麼複雜度可以被限制爲O（NV * V）。

您可以非常粗略地計算出for k循環的複雜度可以是O（avg（A））。這讓我們可以說，整個功能是歐米茄（NV * AVG（A）），其中AVG（A）< = V.

西塔符號（意asympthotical複雜性）將可以像西塔（NV註明* O（V）），O（V）表示一個函數的複雜度，它永遠不會比V增長得快，但不是恆定的。

2014-09-13 16:03:10 3yakuya

回答