使用多个嵌套循环查找Big-O？

Question

int num = n/4;
for (int i = 1; i <= num; i++) {
    for (int j = 1; j <= n; j++) {
        for (int k = 1; k <= n; k++) {
            int count = 1;
        }
    }
}

根据我读过的书,这段代码应该是O((n ^ 3)/ 4).但显然不是.找到嵌套循环的Big-O你应该乘以界限吗？所以这个应该是num*n*n或n/4*n*n.

Answer 1

O((n^3)/4)在大O符号方面毫无意义,因为它意味着将复杂性作为参数的比例来衡量.除以4没有影响,因为它改变了比率的值而不是其性质.

所有这些都是等价的:

O(n^3)
O(n^3/4)
O(n^3*1e6)

其他术语仅在包含术语时才有意义n,例如:

O(n^3 / log(n))
O(n^3 * 10^n)

正如Anthony Kanago正确指出的那样,它的惯例是:

• 只保留总和增长率最高的术语:O(n^2+n) = O(n^2).
• 摆脱产品的常数:O(n^2/4) = O(n^2).

顺便说一句,在所有情况下,我并不总是同意第一条规则.这对于确定函数的最大增长率是一个很好的规则,但是对于算法比较^(a)这样的事情,你可以智能地对输入参数进行限制,就像O(n^4+n^3+n^2+n)明显更糟糕的情况O(n^4).

在这种情况下,应包括任何取决于输入参数的术语.事实上,即使是不变的术语也可能在那里有用.比如O(n+1e100)反对O(n^2)- 后者将在很长一段时间内超越前者,直到n变得足够大以对常量术语产生影响.

^(a)当然,有些人会说它不应该以这种方式使用,但实用主义经常克服现实世界中的教条主义:-)