在c++中...
我知道队列和堆栈的各个函数的时间复杂度，但我不知道同时使用队列和堆栈的 infixToPostfix 函数的时间复杂度是多少......我当然是一名初学者程序员，而且我我很困惑。
我认为使用堆栈和队列从中缀转换为后缀是，Dijkstra 的调车场算法 http://en.wikipedia.org/wiki/Shunting-yard_algorithm。衡量复杂性的一种方法是考虑完成了多少次推送和弹出操作：
- 每个数字都被压入一次并弹出一次。
- 每个运算符都被推送一次并弹出一次。
- 每个令牌仅从令牌队列中出队一次。
- 每个中间结果都只推送一次并弹出一次。
如果字符串的长度为 n，则它有 O(n) 个数字和 O(n) 个运算符，因此前三个组完成的工作量总共为 O(n)。要分析最后一组，请注意每个中间值都来自将两个较早的值组合在一起。如果原始输入中总共有 O(n) 个数字，这意味着可以产生 O(n) 个值作为中介。因此，总运行时间将为 O(n)。
使用像上面这样的参数，从后缀到中缀的转换可以类似地在 O(n) 时间内运行。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
