循环的大O是多少? [英] What is Big O of a loop?

问题描述

我正在阅读有关 Big O符号的信息.它说，

I was reading about Big O notation. It stated,

一个循环的大O是该循环的迭代次数 循环中的语句数.

The big O of a loop is the number of iterations of the loop into number of statements within the loop.

这是一个代码段，

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

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

Now according to the definition, the Big O should be O(n*2) but it is O(n). Can anyone help me out by explaining why is that? Thanks in adavance.

推荐答案

如果检查O()表示法的定义，您会发现常数(乘数)无关紧要.

If you check the definition of the O() notation you will see that (multiplier) constants doesn't matter.

要在循环中完成的工作不是 2.有两个语句，对于每个语句，您必须执行几条机器指令，也许是50或78，或者其他任何指令. ，但这与渐进复杂度计算完全无关，因为它们都是常数.它不依赖于n.就是O(1).

The work to be done within the loop is not 2. There are two statements, for each of them you have to do a couple of machine instructions, maybe it's 50, or 78, or whatever, but this is completely irrelevant for the asymptotic complexity calculations because they are all constants. It doesn't depend on n. It's just O(1).

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

这篇关于循环的大O是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！