1 
void function(int N){
  int c=0;
  for (int i =0; i< N; i+= N/5)
      c++;
}

上面的大O是什么？由于对于每 N 循环将迭代 5 次，它会是 O(1) 吗？

4

4 回答 4

1

由于对于每 N 循环将迭代 5 次，它会是 O(1) 吗？

恰恰。运行时间只取决于一个常数——5——所以它的边界是 O(1)。

于 2013-06-23T10:09:46.370 回答
1

假设例如N = 100。让我们画一个表格：

Iteration |   i
----------+------
    0     |  20
    1     |  40            
    2     |  60
    3     |  80
    4     |  100

请注意，您选择的值无关紧要N，迭代次数最多为 5。因此我们得出结论，i 不依赖于N.

所以..你是对的，它是O(1)。

澄清

上面的例子和循环有什么区别：for(i=0;i<N;i+=20)？

如果你画桌子，你会得到同一张桌子！但是，在这种情况下，结果取决于的值N。如果你选择N = 200，你会得到超过 5 个。所以在这种情况下，结果将是O(N)。

于 2013-06-23T10:10:51.720 回答
0

是的，结果不取决于 N。

于 2013-06-23T10:09:51.147 回答
0

正式回答您的问题如下：

在此处输入图像描述

于 2014-03-18T00:11:52.247 回答