c - 循环的时间复杂度

Question

我不确定以下 C 代码块的复杂性:

int i = 0, j = 1;
for ( i = 0; i < n * n; i += j )
{
    O1();
    j += 2;
}

其中 O1 是一个显然需要常数时间执行的函数。现在，我知道每次迭代计数器增加一个常数的循环通常具有 O(sqrt(n)) 的复杂性，但这里也是这种情况吗？还是O(sqrt(n^2))，即O(n)？

谢谢

Answer 1

I am aware that loops whose counter gets increased by a constant amount every iteration generally have a complexity of O(sqrt(n))

那是假的。每次迭代计数器增加一个常数的循环是 O(N)。

一个循环，其计数器增加的量在每次迭代中线性增加是 O(sqrt(N))。

在这种情况下，这里的 N 是 n * n，因为这是你的循环要循环到的地方，所以这个简单的替换告诉你，是的，操作是O(sqrt(n^2)) 或 O(n)。