Реальный пример экспоненциальной временной сложности

Я ищу интуитивный, реальный пример проблемы, которая требует (наихудшего случая) экспоненциальной сложности времени для решения для беседы, которую я даю.

Вот примеры для других временных сложностей, которые я придумал (многие из них взяты из этого SO-вопроса):

O (1) - определение того, является ли число нечетным или даже
O (log N) - поиск слова в словаре (с использованием двоичного поиска)
O (N) - чтение книги
O (N log N) - сортировка колоды игральных карт (с использованием сортировки слияния)
O (N ^ 2) - проверьте, есть ли у вас все в списке покупок в вашей тележке.
O (бесконечность) - бросает монету, пока она не приземлится на головы.

Любые идеи?

Ответы

Ответ 1

O (10 ^ N): попытка сломать пароль путем тестирования каждой возможной комбинации (при условии, что числовой пароль длины N)

p.s. почему ваш последний пример имеет сложность O (бесконечность)? это линейный поиск O (N).. в мире насчитывается менее 7 миллиардов человек.

Ответ 2

Решение грубой силы задачи коммивояжера является O (n!), которое приблизительно равно O (N ^ N)

Ответ 3

Решение проблемы грубой силы и наивного n-queens.

Вы должны поместить n королев на n * n доску, чтобы их не брали другие.

while there are untried configs, go to next solution and test it

Предполагая, что каждая королева находится в заданной строке, для королевы есть n возможностей и n для (n-1) других ферзей (поскольку повторяющиеся строки не отмечены).

Следовательно, у вас есть сложность O (n ^ n)

Ответ 4

Как найти подмножество целых чисел в наборе, чтобы их сумма была обозначенной величиной X?

Я считаю, что это имеет сложность O (2 ^ (n/2))