algorithm - 如果堆栈操作的时间复杂度为常数 O(1)，则该算法的时间复杂度是多少？

Question

二进制转换: 我们输入一个正整数 n，输出是 n 在堆栈上的二进制表示。

这里的时间复杂度是多少？我认为这是 O(n)，因为 while 循环每次都会减半，这意味着一组输入大小“n”的迭代减少到 n/2、n/4、n/8 等。

应用几何级数之和，其中 n = a 且 r = 1/2，我们得到 2n。

任何帮助表示赞赏!我还是个菜鸟。

create empty stack S
while n > 0 do
    push (n mod 2) onto S
    n = floor(n / 2)
end while
return S

Answer 1

如果循环是

while n>0:
    for i in range n:
        # some action
    n = n/2

那么复杂度就是O(n + n/2 + n/4 ... 1) ~ O(n)，你的答案就是是正确的。

while n > 0 do
    # some action
    n = n / 2

但是，这里的复杂度应该是外部循环运行的次数，因为每次迭代中完成的工作量是O(1)。所以答案将是 O(log(n)) (因为 n 每次都会减半)。