分析堆棧排序算法的時間複雜度

我一直在努力解決編碼面試中的問題，爲一些面試做準備。我能夠解決堆棧分類問題，但我很難找出如何推斷時間複雜性。我的解決方案與本書提供的解決方案非常相似，我已經測試了一下，所以我確定它是正確的。任何對思維過程的深入分析都將非常感謝。這本書說它是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

分析堆棧排序算法的時間複雜度

回答

相關問題