如果堆栈操作是恒定时间o（1），则该算法的时间复杂性是多少？

发布于 2025-01-24 19:23:39 字数 307 浏览 3 评论 0原文

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

原文

BinaryConversion:
We are inputting a positive integer n with the output being a binary representation of n on a stack.

What would the time complexity here be? I'm thinking it's O(n) as the while loop halves every time, meaning the iterations for a set of inputs size 'n' decrease to n/2, n/4, n/8 etc.

Applying sum of geometric series whereby n = a and r = 1/2, we get 2n.

Any help appreciated ! I'm still a noob.

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

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

紫南 2025-01-31 19:23:39

如果循环是循环

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每次都会减半）。

If the loop was

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

Then the complexity would have been O(n + n/2 + n/4 ... 1) ~ O(n), and your answer would have been correct.

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

Here however, the complexity will should be the number of times the outer loop runs, since the amount of work done in each iteration is O(1). So the answer will be O(log(n)) (since n is getting halved each time).

回复收藏 0 原文