什么是循环的大O？

Question

我正在阅读有关Big O符号的内容.它说,

循环的大O是循环迭代到循环内语句数的次数.

这是一段代码片段,

for (int i=0 ;i<n; i++)
{
    cout <<"Hello World"<<endl;
    cout <<"Hello SO";
}

现在根据定义,Big O应该是O(n*2),但它是O(n).任何人都可以解释为什么会帮助我吗？谢谢,谢谢.

Answer 1

如果检查O()表示法的定义,您将看到(乘数)常数无关紧要.

在循环中要完成的工作不是 2.有两个语句,对于每个语句,你必须做几个机器指令,可能是50或78,或者其他什么,但这与渐近的复杂性完全无关计算,因为它们都是常量.它不依赖于n.这只是O(1).

O(1) = O(2) = O(c) where c is a constant.
O(n) = O(3n) = O(cn)

Answer 2

O(n)用于使循环再次成为数学函数(如n ^ 2,n ^ m,..).

所以如果你有这样的循环

  for(int i = 0; i < n; i++) {
     // sumfin
  }

循环所采用的最佳描述数学函数是用O(n)计算的(其中n是0..infinity之间的数字)

如果你有这样的循环

     for(int i =0 ; i< n*2; i++) {

     }

意味着需要O(n*2); 数学函数= n*2

    for(int i = 0; i < n; i++) {
         for(int j = 0; j < n; j++) {

         }
    }

这个循环需要O(n ^ 2)时间; math funciton = n ^ n这样你可以计算你的循环需要多长时间n 10或100或1000

这样您就可以为循环等构建图形.