Nano Hash - криптовалюты, майнинг, программирование

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

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

По сути, у вас есть строка символов «-» и «+»:

++-++++

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

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

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

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, но не могу сформулировать.

java recursion algorithm time-complexity big-o
08.10.2018

  • Ваша серия N..1 вызывается до N раз, так что, думаю, N^2. 09.10.2018
  • это намного хуже (подумайте о Фибоначчи) 09.10.2018

Ответы:


1

В худшем случае первый игрок не может победить, и цикл будет проходить все итерации. Принимая размер задачи 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) возможных строк, полученных из исходной строки, содержащей «+» и «-». После этого все рекурсивные вызовы выполняются с постоянным временем (амортизируются).

09.10.2018
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..