简单的大O复杂性并不总是线性的？

Question

我相信大多数人都知道,如果函数输入大小为n,嵌套循环的复杂度为O(n ^ 2)

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

我认为这是类似的,通过一个类似的论点,但我不确定任何人都可以确认？

for(int i = 0, max = n*n; i < max; i++{
...
}

如果是这样,我猜有些类型的代码,除了递归和子程序之外,其大O映射并不是很明显.

Answer 1

您的基本简单循环始终为O(m),其中m是迭代的上限.但是你的m实际上是n*n,所以它是O(n ^ 2).