以下代码的运行时间是多少

Question

代码如下：

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

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

Answer 1

如果你在谈论渐近符号，Big-Oh，复杂度将是 O(logn)。算一下操作，你会发现它们实际上是以二为底的对数。

渐近符号基本上告诉您该算法并不运行 比给定的复杂度函数慢 。大部分的计算可以直接从代码中看出，但是在更复杂的算法中，需要指令的计算。

Answer 2

您的代码的递归方程：

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

What is the runtime of the following code