Какова временная сложность этого 5-строчного алгоритма Java? - PullRequest
Новая
       28

Какова временная сложность этого 5-строчного алгоритма Java?

0 голосов
/ 09 октября 2018

Это решение следующей проблемы

Обычно у вас есть строка символов '-' и '+':

++- ++++

Вы бросаете два последовательных символа «+» в «-», затем ваш друг делает то же самое, затем возвращается к вам и так далее.Как только кто-то не может сделать ход, он проигрывает.

Так что в вышеприведенной игре, если вы идете первым, вы выигрываете, переворачивая либо последние два «+», либо средние два «+» (подумайтеоб этом).

Вот алгоритм, который решает, выигрывает ли игрок первым или нет: 

public boolean canWin(String s) {
    for (int i = 0; i < s.length() - 1; ++i)
        if (s.charAt(i) == '+' && s.charAt(i + 1) == '+' && 
            !canWin(s.substring(0, i) + "--" + s.substring(i + 2)))
                return true;
    return false;
}

По существу, алгоритм рекурсивно говорит: «Игрок, идущий первым, выигрывает, если он может уменьшитьдоска в состояние, в котором игрок первым теряет ».

Вот мои мысли о сложности времени:

Пусть N будет количеством символов на доске.

В худшем случае есть N-1 ходов (если все '+').Каждый ход делает доску (в худшем случае) всего на 2 хода меньше.

Но тогда я застреваю.Я знаю, что это хуже, чем N * (N-2) * (N-4) * ... * 1, но я не могу сформулировать это.

1 Ответ

0 голосов
/ 09 октября 2018

В худшем случае первый игрок не может выиграть, и цикл пройдет все итерации.Принимая размер задачи n за число плюсов во входной строке, мы имеем время выполнения T (n) = (n-1) T (n-2) = (n-1) (n-3)Т (п-4) = ... = О (п !!).Здесь н!является двойным факториалом.Это значительно хуже экспоненциального, что для этой проблемы довольно страшно.Вы можете немного улучшить эту границу, используя динамическое программирование, следующим образом: 

Set<String, Boolean> canWinMap = new HashMap<>();

public boolean canWin(String s) {
    if (canWinMap.hasKey(s)) {
        return canWinMap.get(s);
    }
    for (int i = 0; i < s.length() - 1; ++i)
        if (s.charAt(i) == '+' && s.charAt(i + 1) == '+' && 
            !canWin(s.substring(0, i) + "--" + s.substring(i + 2)))
                canWinMap.put(s, true);
                return true;
    canWinMap.put(s, false);
    return false;
}

Тогда наихудший случай ограничен экспоненциальным (возможно, умноженным на линейный член), поскольку существует только O (2 ^ n) возможные строки, полученные из начальной строки, содержащей «+» и «-».После этого все рекурсивные вызовы являются постоянными (амортизируются).

...