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

Question

我认为它应该是二次的，即 O(n^2)。我正在阅读此来源 prefix to postfix 。我假设追加两个字符串需要线性时间（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('[=11=]');
            continue;
        }
        dest.append(c);
        // done expression.  check the todo stack
        while(!stk.empty())
        {
            c = stk.pop();
            if (c=='[=11=]')
            {
                break;
            }
            dest.append(c);
            // the append completed another expression, so loop
            // to check the todo stack again
        }
    }
    return dest.toString();
}

这是递归的直接转换。

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

Time complexity of prefix to postfix conversion?

stack

time-complexity

postfix-notation

data-structures