代码的时间复杂度是多少？

下面的代码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

回答