该循环的时间复杂性是多少

Question

int count=0;
do
{
    count++;
    n=n/2;
}while (n>1);

我在这里看到模式很难。
即使插入n的数字，然后绘制每个基本操作。
预先感谢！

编辑：我想要这里最坏的情况。

Answer 1

第一步是用 2将n分配。因此，您得到n/2。现在，如果n/2 > 1，则将其再次分配给2，然后获得n/4。如果n/4 > 1您再次这样做，并且会得到n/8，或者更好地将其写入n/(2^3) ...现在，如果n/(2^3) > 1，则再次进行n/(2^4) ...因此，如果您这样做k次，则获得n/(2^k)。如何将k计算为n/(2^k) ≤ 1？简单：

n/(2^k) ≤ 1
n ≤ 2^k
ln(n) ≤ k

所以，您的算法需要O(ln(n))迭代才能退出循环。

在您的代码中，k是count。