前缀到后缀转换的时间复杂度?

Question

我认为它应该是二次的，即O(n^2(。我正在从这个源前缀读取后缀.我假设附加两个字符串需要线性时间(O(我们正在附加的两个字符串的大小之和((，我们需要追加的最大次数可以达到 O(n(，因此整体复杂度为 O(n^2(。 有人能说出我是否错了，有人能提供更好的证据吗？

Answer 1

是的，你是对的，它是 O(n²(，我认为你的证明是可以的，但这取决于你必须向谁证明它。 也许明确地展示如何构造一个字符串，该字符串将导致 O(n( 大小的 O(n( 附加。

这是一个在 O(n( 中完成工作的简单递归版本：

static String preToPost(String src)
{
StringBuilder dest = new StringBuilder(src.length());
for(int pos=0; pos < src.length(); pos = preToPost(dest, src, pos));
return dest.toString();
}
// Convert one prefix expression to postfix.  Returns
// end position
static int preToPost(StringBuilder dest, String src, int pos)
{
if (pos >= src.length())
{
//no expression
return pos;
}
char c = src.charAt(pos++);
if ("+-/*".indexOf(c)>=0)
{
//operator. Convert both operands first
pos = preToPost(dest, src, pos);
pos = preToPost(dest, src, pos);
}
dest.append(c);
return pos;
}

迭代版本并没有复杂得多：

static String preToPost2(String src)
{
StringBuilder dest = new StringBuilder(src.length());
int pos=0;
Stack<Character> stk = new Stack<>();
while(pos < src.length())
{
char c = src.charAt(pos++);
if ("+-/*".indexOf(c)>=0)
{
//operator.  After the next 2 expressions, put c
stk.push(c);
//after the next expression, just do another one
stk.push('');
continue;
}
dest.append(c);
// done expression.  check the todo stack
while(!stk.empty())
{
c = stk.pop();
if (c=='')
{
break;
}
dest.append(c);
// the append completed another expression, so loop
// to check the todo stack again
}
}
return dest.toString();
}

这是递归的直接转换。