这段代码的时间复杂度是多少？
int count=0;
for(int I=N;I>0;I=I/2)
{
for(int j=0;j<I;j++)
{
count=count+1;
}
}
请解释清楚
内部循环进行 n 次迭代，然后是 n/2，然后是 n/4，等等。
i =n n/2 n/4 n/8 ....................logn times
j=n n/2 n/4 n/8 ...........logn tmes
T(n) = n+ n/2 + n/4 + n/8 + ...........logn time
= n(1+ 1/2 + 1/4 + .............logn times) Decreasing GP
=O(n)
所以，
时间复杂度为
O(n)
要了解有关几何系列的更多信息，请参阅此文档
这里让我们举个例子：
让 n = 10
最初：i = 10（第一次循环）
j = 0 < 10(i) so it will loop from 0 to 9 times
现在在嵌套循环结束之后
i /= 2
SO 值 i = 5（第一次循环）2 次迭代。
这次 j 将从 j = 0 < 5(i) 开始运行，因此它将从 0 到 5 次循环
每次 i 的值将除以 2，类似地，j 的相应值将从 0 迭代到 i/2 次。
所以，T(n) = O(n + n/2 + n/4 + … 1) = O(n)对于 j （这仅用于 j 的迭代）
i j
10 0-9 times
5 0 - 4 times
2 0 - 1 times
同样，最初为 n 的 j 值，即 10 在 n/2 形成 GP 时按顺序递减，因此我们得到O(n)
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句