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

Question

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

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

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

Есть идеи?

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

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

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