我现在在上算法课以下是我在一次测验中弄错的一个问题:基本上,我们必须用大O符号表示最坏的运行时间:
int foo(int n)
{
m = 0;
while (n >=2)
{
n = n/4;
m = m + 1;
}
return m;
}
我不明白这件事最糟糕的时候怎么不是O(n)请解释一下谢谢。
最佳答案
foo
通过将n
除以4计算log4(n),并使用n
作为计数器计算m
中的4。最后,m
将是n
中的4因此,它在最终值m
中是线性的,等于n
的对数基4。算法是O(logn)
,也就是O(n)
。