使用隊列和堆棧將中綴轉換爲後綴的運行時間是多少？

Question

在C++ ... 我知道隊列和堆棧的單個函數的時間複雜性，但我不知道使用隊列和堆棧的infixToPostfix函數的時間複雜度是多少....我是一個初學程序員，當然，我很困惑。

Answer 1

使用堆棧和隊列從中綴轉換爲後綴我假設Dijkstra's shunting-yard algorithm。衡量複雜性的一種方法是考慮完成了多少次推送和彈出：

• 每個數字都被精確推入一次，並彈出一次。
• 每個操作員都被精確推入一次並彈出一次。
• 每個令牌只從一個令牌隊列中出列一次。
• 每個中間結果都會被精確推送一次並彈出一次。

如果您的字符串長度爲n，那麼它有O（n）個數字和O（n）運算符，因此這些組中前三個所做的工作總數將爲O（n）。要分析最後一組，請注意，每個中間值都來自兩個較早值的組合。如果在原始輸入中總共有O（n）個數字，這意味着可能存在作爲中介產生的O（n）值。因此，總運行時間將是O（n）。

從後綴轉換爲中綴可以類似地顯示在O（n）時間使用像上面那樣的參數運行。

希望這會有所幫助！