什么是复杂性:
int f4(int n)
{
int i, j, k=1, count = 0;
for(i = 0; i < n; i++)
{
k *= 3;
for(j = k; j; j /= 2)
count++;
}
return count;
}
我知道它是 O(n^2) 但你如何计算这个?为什么不是 n*log n?
什么是复杂性:
int f4(int n)
{
int i, j, k=1, count = 0;
for(i = 0; i < n; i++)
{
k *= 3;
for(j = k; j; j /= 2)
count++;
}
return count;
}
我知道它是 O(n^2) 但你如何计算这个?为什么不是 n*log n?
有 n 个外循环。在任何时候,。有内部循环(因为我们在每次迭代中减半。)k = 3i
log2(k)
j
log2(3i) = log3 (3i) / log3(2) = i / (constant)
所以内循环的复杂度是i
。换句话说,这个程序具有相同的复杂性(但不完全相同的迭代次数)
int f4changed(int n)
{
int i, j, count = 0;
for(i = 0; i < n; i++)
{
for(j = 0; j < i; j++)
{
count++;
}
}
}
正如您已经看到的那样。O(n2)
i = 1 导致 3 次迭代(内部循环) (3, 1, 0)
i = 2 是 8 (5 然后 3)
i = 3 是 13 (7 + 5 + 3)
您所拥有的是近似算术级数,即 O(n 2 )。
为了完整起见(并解释为什么确切的迭代次数无关紧要),请参阅Big O 的普通英语解释(这对于其他读者来说比你更适合,因为你似乎知道发生了什么,所以发帖者)。
Log(Pow(3,n)) ~ O(N) 的复杂度。如果内部循环是 k *= 2,那么迭代次数也将是 n。
为了计算 O(~),使用最高幂项,而忽略其他项。Log(Pow(3,n)) 可以定义为:
Log(Pow(2,n)) <= Log(Pow(3,n)) <= Log(Pow(4,n))
现在 Log(Pow( 4,n)) = 2*Log(Pow(2,n))。
这里的最高幂项是 n(因为 2 是常数)。