O(n) решения для решения проблемы
Какова наилучшая временная сложность O(n) функции, которая решает непростую задачу, где задвижка равна n на n?
Я чувствую, что это n^2 так как для каждого персонажа мы должны смотреть на 2(n-1) другие персонажи. Интервьюер утверждал, что это не n^2 для O(1) поиск по словарю.
3 ответа
Я наконец-то понял. Ответ оказывается экспоненциальным во времени.
Представьте себе решетку 4X4
ABCD
EFGH
IJKL
MNOP
Тогда, например, любая из упорядоченных подпоследовательностей, начинающихся с A в ABCDHGFEIJKLPONM это потенциальное слово; как и любая из упорядоченных подпоследовательностей, начинающихся с A в AEIMNOPLHDCBFJKG или AEIMNOPLHGFIK или ABCDHLPONMIEFGKJ. Затем нам нужно посмотреть на потенциальные слова, начиная с B, затем с C и т. Д.
Давайте посмотрим на это по-другому. Скажем, мы должны были только рассмотреть _ABCD, где _ представляет некоторый начальный персонаж, скажем X; тогда потенциальные слова, которые относятся к набору мощности:
XD; XC; XCD; XB; XBD; etc.
Следовательно, рассматривая только спирали по часовой стрелке, начинающиеся с каждого символа, мы уже смотрим на n^2*2^(n-1), n^2 потому что сетка n by n и так для 4 by 4 В сетке есть 16 возможных стартовых символов. А также 2^(n-1) из-за powerset во главе с каждым стартовым персонажем. Конечно, спираль по часовой стрелке - не единственная возможная модель. Но мы уже можем видеть временную сложность с этим первым паттерном: Big-Omega(2^n), который экспоненциальный.
Посмотрите на http://exceptional-code.blogspot.com/2012/02/solving-boggle-game-recursion-prefix.html. Решением динамического программирования является O(D), где D - размер словаря.
Не очень понятно, на что способен словарь.
Немного глупо, но на мой взгляд правильный ответ таков:
Поскольку в boggle слова могут идти произвольным образом (от каждого символа до любых смежных (горизонтальных, вертикальных или диагональных) символов, которые еще не используются в этом слове), для слова длины L, словосочетания могут быть до 8^L если вы не устраните комбинации, где символы появляются несколько раз. Во всяком случае, учитывая L чтобы быть постоянным (поскольку используемый словарь является постоянным), это значение также является постоянным. Подводя итог, поиск слова (ей), начиная с заданной позиции, имеет временную сложность: O(1),
Итак, что остается, это начальная позиция слова, которое находится в пространстве n^2, так что ваш решатель имеет сложность времени O(n^2) и ты прав.
Как уже было сказано, я считаю эту аргументацию немного глупой.
Проблема может заключаться в том, что никто не хочет считать словарь постоянным, потому что он очень большой. Предполагая, что он бесконечно большой, но он реализует O(1) поиск существующих слов (это ЕДИНСТВЕННЫЙ запрос, который мы можем использовать для словаря, особенно нет поиска префиксов слов), и далее предположим, n Чтобы не быть ограничивающим фактором по сравнению с длиной слова, сложность времени является экспоненциальной. Но я думаю, что предположение о том, что поиск успешен только для существующих слов, неверно в этом упражнении.
Другим возможным предположением может быть то, что в словаре есть поиск префиксов слов (который возвращает, существуют ли слова, которые начинаются с данной строки, но не обязательно совпадают со строкой). В этом случае мы могли бы реализовать лучший и гораздо более сложный алгоритм, который ищет ограниченное пространство поиска (используя каждый символ не более одного раза). Ограничивающим фактором длины слова будет n^2, поскольку ни одно слово (содержащееся в текущей доске) не может быть длиннее этого (потому что мы можем использовать каждый символ только один раз). Опять стартовые позиции в космосе n^2Таким образом, глупый алгоритм на основе пути будет иметь временную сложность O(n^4)Значит, ты не прав. В настоящее время я не могу придумать алгоритм с лучшей временной сложностью при этих предположениях.