代码之家 › 专栏 › 技术社区 › Rayyan Khan

如果堆栈操作是常数时间O(1),那么该算法的时间复杂度是多少?

theory big-o time-complexity data-structures algorithm

0

Rayyan Khan · 技术社区 · 4 年前

二进制转换: 我们输入一个正整数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

0 回复 | 直到 4 年前

1

3

Abhinav Mathur 4 年前

如果循环是

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 每次减半)。

2

0

Ashwin Ganesan 4 年前

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