本文介绍了循环的时间复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我不确定以下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)。
更多推荐
循环的时间复杂性
发布评论