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

我一直在努力解决编码面试中的问题，为一些面试做准备。我能够解决堆栈分类问题，但我很难找出如何推断时间复杂性。我的解决方案与本书提供的解决方案非常相似，我已经测试了一下，所以我确定它是正确的。任何对思维过程的深入分析都将非常感谢。这本书说它是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())

作为一个方面说明：我用这个方法到堆栈中进行排序是问题的约束范围内。我知道存在更快的解决方案。

预先感谢您。

来源

2016-09-16 rocktheartsm4l

外环至少有n次迭代，我知道。根据值，内部循环可以有0和temp_stack.size迭代。在最坏的情况下，原始堆栈已经排序，我们将有0 + 1 + 2 + 3 + ...（n-1）次迭代......但是我认为这个求和结果为n（n + 1）/ 2，当我们忽略它自己的n^2的常量时。我以为我在做什么，但现在我不确定。 – rocktheartsm4l

或将内部循环的分析为：1/n + 2/n + 3/n + 4/n + ...（n-1）/ n我们认为它只是n？我要睡觉很晚了< – rocktheartsm4l

考虑最糟糕的情况，其中排序堆栈中的每个项目都需要完全清空临时堆栈。（这种情况发生在尝试对排序后的堆栈进行排序时）。

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

结合这些应该给O（n^2）。

来源

2016-09-16 05:34:13

第1项需要0次临时堆栈弹出，第2项需要1次弹出，第3项需要2次弹出...项目n需要n-1次弹出。所以总共我们有1 + 2 + 3 + 4 + 5 + ..... + N个内循环迭代。即N（N + 1）/ 2或1/2（N^2 + N）是O（n）。我认为我所做的是在外部循环时，将外部循环考虑在内时错误地将其乘以N。我一直得到O（N^3）。 – rocktheartsm4l

是的，这个总和已经计算了临时堆栈弹出的总数。虽然它不包括将“已看到”项目推回到临时堆栈，但将其加倍以包含它并不会改变整体的复杂性。从逐行分析代码退后一步，我想到了这样的情况：您看到的每个新项都需要O（n）弹出/推入才能将其插入到临时堆栈中。重复n次得到O（n^2）。 –

感谢您指出推动。起初我不认为他们会把工作翻倍，但后来我意识到我必须再次推动每一个流行！我理解你的观点，尽管在渐进分析中，双倍的工作并不影响我们的整体复杂性。谢谢你的时间:) – rocktheartsm4l

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

来源

2016-09-16 05:09:13 denvaar

这在很多情况下都有效，但我同意这是一种过于简化的方法。这本书指出，记住你提到的'模板'并不是一个深刻的理解。谢谢你的反馈！ – rocktheartsm4l

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

回答

相关问题