如果堆栈操作是常数时间O(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 每次减半)。

迭代次数是将n除以2得到0的次数,也就是O(logn)。