堆栈排序技术的时间复杂度？

Question

假设我有以下伪代码：

while A is not empty and stack top of A is less than x:
    pop A and push the returned value onto B
push x onto A
while B is not empty:
    pop B and push the returned valued onto A

say stacks A and B are initially empty. Insert n numbers with a new number x each time using the above algorithm, what would be worst time complexity.

我能够得到这个算法将长度为 n 的插入数字从最小（顶部）到最大（底部）排序，最好的情况是 n 当插入的数已经排好了，从大到小。但我不明白最坏的情况是 O(n^2).

Answer 1

插入 n 个元素而不排序将是 o(n)。由于每个排序是 o(n)，因此总数是 O(n^2)。最坏的情况：数字以相反的顺序显示。

Answer 2

如您所知，此算法使用 2 个堆栈对项目集合进行排序。

在每一步，它都会从 A 弹出项目，然后将其推入 B，直到找到正确的位置。然后它从 B 弹出并推回 A.

这意味着在第 n 步，最多有 2*(n-1)+1 个操作。

如果初始集合是反向排序的，每次插入都会发生这种情况，使得复杂度 O(N²)。

Answer 3

对于每次插入，最好的情况是当 StackTop[A]>x 时，它只会将 x 推入 A，而 B 将清空。因此，在最佳情况下，每次插入的时间复杂度为 o(1)。所以对于 n 个元素 o(n)

现在假设元素以递增顺序插入，那么每次插入都会导致堆栈 A 被清空并放入 B。
在此之后将 x 插入到 A 中，然后将堆栈 B 元素放入 A 中，一个一个地弹出和推送。每次插入都需要 o(n)。所以对于 n 插入 o(n^2).

Answer 4

最坏的情况：
让我们以输入 {1,2,3,4}
为例 第一步:(x=1)
最初 A,B 是空的。所以通过算法 A{1}, B{}.
step2:(x=2)
通过算法 B={1}、A ={2} 然后 A={1,2} B={}.
步骤 3:(x=3)
按算法最初 B={2,1} A={3} 然后 A={3,2,1} B={}.
step4:(x=4)
按算法最初 B={1,2,3} A={4} 然后 A={4,3,2,1} B={} 每一步的成本是 (2*(n-1))，其中 n 是输入的大小。
所以如果我们总结最坏情况时间复杂度是 O(n^2)

堆栈排序技术的时间复杂度？

time complexity for a sorting technique for stacks?

sorting

algorithm

big-o

stack

time-complexity