Преобразование из инфикса в постфикс с использованием стека и очереди, я полагаю, Алгоритм маневрирования Дейкстры .Один из способов измерить сложность состоит в том, чтобы подумать о том, сколько нажатий и щелчков сделано:
- Каждое число нажимается ровно один раз, а выталкивается ровно один раз.
- Каждый оператор нажимается ровно один рази выдается ровно один раз.
- Каждый токен исключается из очереди токенов ровно один раз.
- Каждый промежуточный результат отправляется ровно один раз и выдается ровно один раз.
Если ваша строка имеет длину n, то она имеет O (n) чисел и O (n) операторов, поэтому общий объем работы, выполненной первыми тремя из этих групп, будет O (n).Чтобы проанализировать последнюю группу, обратите внимание, что каждое промежуточное значение получается из объединения двух более ранних значений.Если в исходном входе имеется общее количество чисел O (n), это означает, что в качестве посредников могут быть получены значения O (n).Следовательно, общее время выполнения будет равно O (n).
Аналогично может быть показано, что преобразование из постфикса в инфикс может выполняться за время O (n) с использованием аргумента, подобного приведенному выше.
Надеждаэто помогает!