分析堆栈排序算法的时间复杂度

Question

我一直在解决 Cracking the Coding Interview 中的问题，为一些面试做准备。我能够解决堆栈排序问题，但我真的很难弄清楚如何推理时间复杂度。我的解决方案与书中提供的解决方案非常相似，我已经对其进行了大量测试，因此我确信它是正确的。任何对分析该算法的思维过程的深入了解都将不胜感激。书上说是O(n^2)。这是算法：

def sort_stack(stack):
    temp_stack = Stack()
    while not stack.is_empty():
        v = stack.pop()
        if temp_stack.is_empty() or temp_stack.peek() <= v:
            temp_stack.push(v)
        else:
            while not temp_stack.is_empty() and temp_stack.peek() > v:
                stack.push(temp_stack.pop())
            temp_stack.push(v)
    while not temp_stack.is_empty():
        stack.push(temp_stack.pop())

附带说明：我使用这种方法对堆栈进行排序，以便在问题的约束范围内。我知道存在更快的解决方案。

提前致谢。

Answer 1

这可能是一种过于简化的算法分析方法，但每当我看到嵌套循环时，我都会想到 n^2。三个嵌套循环——n^3 等。作为简单程序的经验法则，计算嵌套循环数。这是一个非常有用的教程：http://cs.lmu.edu/~ray/notes/alganalysis/

Answer 2

考虑最坏的情况，对堆栈中的每一项进行排序需要完全清空临时堆栈。（当尝试对反向排序的堆栈进行排序时会发生这种情况。）

每个项目的 emptying/refilling 临时堆栈的成本是多少？
有多少项？

结合这些应该得到 O(n^2)。

分析堆栈排序算法的时间复杂度

Analyzing a stack sort algorithm's time complexity

python

sorting

algorithm

big-o

stack