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

Question

BinaryConversion：我们输入一个正整数 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每次都减半）。