Временная сложность преобразования префикса в постфикс? - PullRequest
Новая
       27

Временная сложность преобразования префикса в постфикс?

1 голос
/ 09 февраля 2020

Я думаю, что это должно быть квадратично c то есть O (n ^ 2). Я читаю из этого источника префикс к постфиксу . Я предполагаю, что добавление двух строк занимает линейное время (O (сумма размера двух строк, которые мы добавляем)), и максимальное количество раз, которое нам нужно добавить, может go до O (n), и, таким образом, общая сложность равна O ( п ^ 2). Может кто-нибудь сказать, если я не прав, и кто-то может предоставить лучшее доказательство этого?

1 Ответ

0 голосов
/ 09 февраля 2020

Да, вы правы, что это O (n 2 ), и я думаю, что ваше доказательство в порядке, но это зависит от того, кому вы должны это доказать. Может быть, показать явно, как построить строку, которая привела бы к 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('\0');
            continue;
        }
        dest.append(c);
        // done expression.  check the todo stack
        while(!stk.empty())
        {
            c = stk.pop();
            if (c=='\0')
            {
                break;
            }
            dest.append(c);
            // the append completed another expression, so loop
            // to check the todo stack again
        }
    }
    return dest.toString();
}

Это прямое преобразование рекурсивного.

...