Я ищу интуитивный, реальный пример проблемы, которая требует (наихудшего случая) экспоненциальной сложности времени для решения для беседы, которую я даю.
Вот примеры для других временных сложностей, которые я придумал (многие из них взяты из этого SO-вопроса):
- O (1) - определение того, является ли число нечетным или даже
- O (log N) - поиск слова в словаре (с использованием двоичного поиска)
- O (N) - чтение книги
- O (N log N) - сортировка колоды игральных карт (с использованием сортировки слияния)
- O (N ^ 2) - проверьте, есть ли у вас все в списке покупок в вашей тележке.
- O (бесконечность) - бросает монету, пока она не приземлится на головы.
Любые идеи?