9! × 49,

9! × 4⁹,

где 9! обозначает произведение 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1, которое называют «9 факториал». Если компьютер может проверять по 100 миллионов вариантов в секунду, перебор всех этих возможностей займет у него чуть больше 15 минут. Не так уж и плохо. Но посмотрите, как быстро это время увеличивается с ростом числа плиток. Возьмем 16 плиток, которые нужно уложить в квадрат 4 × 4. Из рассуждений, аналогичных приведенным выше, следует, что число возможных комбинаций равно

16! × 416

16! × 4¹⁶

Это увеличивает время, необходимое для перебора всех этих вариантов, до 28,5 миллиона лет. Если же перейти к простому квадрату 5 × 5, оно превысит возраст Вселенной, составляющий всего-навсего 13,8 миллиарда лет.

Число возможных конфигураций сетки с n положениями определяется формулой n! × 4ⁿ. Функция 4ⁿ растет с увеличением n экспоненциально. Я уже рассказывал о том, как опасен рост этой функции, в главе 1, когда индийский царь должен был заплатить за изобретение шахмат рисовыми зернами, число которых экспоненциально увеличивалось по мере продвижения по клеткам шахматной доски. А факториал n! (произведение всех чисел от 1 до n) – это функция, рост которой на самом деле еще быстрее экспоненциального.

Таково математическое определение длинного пути: алгоритм решения задачи, время работы которого, необходимое для вычисления ответа, экспоненциально возрастает с увеличением размера задачи. Именно для таких задач хотелось бы найти шорткаты. Но что считать качественным шорткатом? Так можно назвать алгоритм, по-прежнему вычисляющий решение сравнительно быстро даже при увеличении размера задачи: так называемый алгоритм полиномиального времени.

Предположим, у меня есть случайный набор слов, которые я хочу расположить в алфавитном порядке. Сколько времени будет занимать эта работа по мере все большего удлинения списка слов? Простой алгоритм для решения этой задачи мог бы в начале просмотреть весь исходный список из N слов и выбрать из него слово, стоящее в словаре раньше всех остальных. Затем нужно повторить ту же операцию для оставшихся N – 1 слов. Таким образом, чтобы расставить по порядку все N слов, нужно будет перебрать N + (N – 1) + (N – 2) + … + 1 слово. Но благодаря шорткату Гаусса мы знаем, что для этого потребуется в общей сложности N × (N + 1)/2 = (N² + N)/2 просмотров.