循环的时间复杂性

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

我知道每次迭代计数器增加一个常量的循环通常具有O(sqrt(n))的复杂度

那是假的.每次迭代计数器增加一个恒定量的循环是O(N).

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

在这种情况下,N这就是n * n你的循环直到循环,因此简单的替换告诉你,是的,操作是O(sqrt(n ^ 2))或O(n).