以下代码的运行时是什么

Question

代码如下：

Ans = 1;
while( N > 0)
{
     Ans = Ans*2;
     N = N/2;
 }

我不知道N=N/2将如何影响运行时间。我试图通过检查如果N=1，循环会运行多少次来找到一个模式。。7但是我没有注意到任何模式。我想我一定是搞错了。

Answer 1

如果你谈论的是渐近记数法，那么大哦，复杂度将是O(logn)。计算这些运算，你会发现它们实际上是以2为底的对数。

渐近记数法基本上告诉你，算法的运行速度不会比给定的复杂度函数慢。大多数计算都可以立即从代码中看到，但在更复杂的算法中，需要计算指令。

Answer 2

代码的递归方程：

T(n)=T(n/2)+O(1)
Time complexity is O(logn)