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

Question

我一直在努力解决破解编码面试的问题，为一些面试做准备。我能够解决堆栈排序问题，但我很难找到如何解释时间复杂性的方法。我的解决方案非常类似于书中提供的解决方案，我已经对它进行了相当多的测试，所以我确信它是正确的。任何对思维过程的洞察力，都将是非常感谢的，我们将通过这个过程来分析这个算法。书上说是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

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

清空/重新填充每个项目的临时堆栈的成本是多少？

有多少件物品？

将它们结合在一起就可以得到O(n^2)。

Answer 2

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