大O:为什么这些循环的时间复杂度是 O(N)?
-
29-09-2020 - |
题
我有以下功能。
int fun(int n)
{
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
它有 O(N)
时间复杂度。我以为是 O(N LogN)
(IE。如果我们删除内循环,我们会得到)
for (int i = n; i > 0; i /= 2){
...
}
这是 O(Log N)
不是吗?内循环结果是 O(N)
因为它只是线性增加。所以我认为应该是 O(Log N * N)
. 。我的想法可能出了什么问题?
解决方案
查看内循环执行了多少步。它是 $n + \frac{1}{2}n + \frac{1}{4}n + \cdots$. 。但是,那 几何系列 告诉我们:
$$\sum_{k=0}^{\lceil\log n ceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2 ^k} = 2n$$
不隶属于 cs.stackexchange