我不确定以下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)？
谢谢
我知道循环的计数器每次迭代都会增加一个固定的数量，其复杂度通常为O（sqrt（n））
错了 一个循环，其每次计数的计数器增加恒定量的循环为O（N）。
一个循环，其计数器增加的次数在每次迭代中线性增加，即为O（sqrt（N））。
在这种情况下，N这里是n * n，因为这是循环一直循环到的内容，这样简单的替换就可以告诉您，是的，操作是O（sqrt（n ^ 2））或O（n）。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句