中缀前缀时间和空间复杂度

Question

我一直在努力编写一个Java程序，使用操作数堆栈和操作堆栈从中缀表示法转换为前缀表示法。我已经实现了一个基于伪这里最多的回答工作转换器：

conversion from infix to prefix

不过我现在正在想办法了时间和空间的上述算法的复杂性。

我认为空间复杂性必须是O（n），因为我们只有两个堆栈来存储它们之间共享的输入。

考虑时间复杂性，我不完全确定，是否因为必须将每个子部分从中缀转换为前缀而导致O（n^2）？我不确定这部分。

基本上我的问题是：我的空间复杂度结果是否正确，算法的时间复杂度是多少？

非常感谢！

编辑： 这是算法的伪代码：

Algorithm ConvertInfixtoPrefix 

Purpose: Convert and infix expression into a prefix expression. Begin 
// Create operand and operator stacks as empty stacks. 
Create OperandStack 
Create OperatorStack 

// While input expression still remains, read and process the next token. 

while(not an empty input expression) read next token from the input expression 

// Test if token is an operand or operator 
if (token is an operand) 
// Push operand onto the operand stack. 
    OperandStack.Push (token) 
endif 

// If it is a left parentheses or operator of higher precedence than the last, or the stack is empty, 
else if (token is '(' or OperatorStack.IsEmpty() or OperatorHierarchy(token) > OperatorHierarchy(OperatorStack.Top())) 
// push it to the operator stack 
    OperatorStack.Push (token) 
endif 

else if(token is ')') 
// Continue to pop operator and operand stacks, building 
// prefix expressions until left parentheses is found. 
// Each prefix expression is push back onto the operand 
// stack as either a left or right operand for the next operator. 
    while(OperatorStack.Top() not equal '(') 
     OperatorStack.Pop(operator) 
     OperandStack.Pop(RightOperand) 
     OperandStack.Pop(LeftOperand) 
     operand = operator + LeftOperand + RightOperand 
     OperandStack.Push(operand) 
    endwhile 

// Pop the left parthenses from the operator stack. 
OperatorStack.Pop(operator) 
endif 

else if(operator hierarchy of token is less than or equal to hierarchy of top of the operator stack) 
// Continue to pop operator and operand stack, building prefix 
// expressions until the stack is empty or until an operator at 
// the top of the operator stack has a lower hierarchy than that 
// of the token. 
    while(!OperatorStack.IsEmpty() and OperatorHierarchy(token) lessThen Or Equal to OperatorHierarchy(OperatorStack.Top())) 
     OperatorStack.Pop(operator) 
     OperandStack.Pop(RightOperand) 
     OperandStack.Pop(LeftOperand) 
     operand = operator + LeftOperand + RightOperand 
     OperandStack.Push(operand) 
    endwhile 
    // Push the lower precedence operator onto the stack 
    OperatorStack.Push(token) 
endif 
endwhile 
// If the stack is not empty, continue to pop operator and operand stacks building 
// prefix expressions until the operator stack is empty. 
while(!OperatorStack.IsEmpty()) OperatorStack.Pop(operator) 
OperandStack.Pop(RightOperand) 
OperandStack.Pop(LeftOperand) 
operand = operator + LeftOperand + RightOperand 

OperandStack.Push(operand) 
endwhile 

// Save the prefix expression at the top of the operand stack followed by popping // the  operand stack. 

print OperandStack.Top() 

OperandStack.Pop() 

End 

Answer 1

是的，为O（n^2）看起来是正确的 - 因为基本上你有一个外部和内部while循环。

编辑：O（m * n个），其中m < = n，但还是二次型