本文介绍了循环的时间复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我不确定以下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(N)。
计数器在每次迭代中线性增加的循环为O(SQRT(N))。
在本例中，N是n * n，因为这就是循环要循环到的位置，所以简单的替换告诉您，是的，操作是O(sqrt(n^2))或O(N)。
这篇关于循环的时间复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！