0

让 A 是一个数组[1..n]，其中有零和一。func ()是复杂度为 theta(m) 的函数。对于给定的伪代码，复杂度是多少？

  counter=0;
    for(i=0;i<n;i++)
       {
          if(a[i]==1)
           counter++;
         else
           func();
   }

根据我的说法，函数 func() 最多被调用 n 次的最坏情况是当数组完全用 zeros 填充时。因此，由于 func() 的 theta 命名为 theta(m)

上述代码的复杂性是 :theta(mn) ....??? 如果没有，请帮助我进行适当的验证。

4

1 回答 1

0

上述代码的时间复杂度将是O(mn) (Big O mn)。
为什么？
正如你所说的 func() 是 theta(m) 现在在计算时间复杂度时，正如你自己指出的那样，最坏的情况是 func 被调用 n 次将导致 O(mn)。
为什么不是 Theta(mn)？
Theta 对时间复杂度有更严格的限制。这不仅意味着它总是在最坏的情况下执行 mn*，而且在最好的情况下执行 mn* （*给或取一个乘法或加法常数）。所以它与输入成比例地增加。但是，我们不能保证 omega(mn) 的下限（aka omega）。
去这里查找有关大 O 与大 Theta 的更多信息

您应该能够回答为什么我们不能自己保证 Theta(mn) 的下限。

最好的，迪格维杰

于 2013-10-27T07:24:12.287 回答