«О» большое: эталон для худшего случая
Чешский иллюзионист Зденек Брадак попал в Книгу рекордов Гиннесса, установив рекорд по сортировке колоды карт. 15 мая 2008 года Брадак смог разложить в правильном порядке колоду из 52 карт всего за 36,16 секунды[7]. Как ему это удалось? Какую технику сортировки он применял? И хотя его ответ, очевидно, пролил бы свет на теорию сортировки, сам Брадак воздержался от комментария. Мы, несомненно, уважаем мастерство и ловкость маэстро, но при этом мы на 100 % уверены, что можем побить его рекорд. По сути, мы уверены на 100 %, что можем поставить рекорд, который никто не сможет побить. Все, что нам нужно, – это около 80 658 175 170 943 878 571 660 636 856 403 766 975 289 505 440 883 277 824 000 000 000 000 попыток в борьбе за звание рекордсмена. Это число, значение которого немного больше 80 унвигинтиллионов (52 факториал, или 52! в математическом обозначении), – число возможных перестановок в колоде карт. Предпринимая такое количество попыток, вы рано или поздно обязательно сложите колоду в правильном порядке, при этом абсолютно случайно. Таким образом, теперь мы можем с гордостью вписать в Книгу рекордов Гиннесса имя Кристиана Гриффитса, выступившего с не таким уж и плохим временем – 0 минут 0 секунд. По правде говоря, таким способом мы бы точно пытались установить новый рекорд до конца света. Тем не менее этот факт явно указывает на огромные фундаментальные различия между рекордсменами и учеными-компьютерщиками. Именитые господа из Книги рекордов Гиннесса беспокоятся только о показателях в наилучшем случае. Конечно, едва ли их можно винить за это, ведь все спортивные рекорды – не что иное, как показатели одного лучшего выступления. Однако информатику практически никогда не волнует наилучший случай. Вместо этого ученые хотели бы знать, сколько в среднем занимает тасование карт у того же Брадака: было бы здорово заставить его тасовать колоду все 80 унвигинтиллионов раз (или что-то в этом роде) и оценивать его по средней скорости на протяжении всех попыток (теперь вы понимаете, почему программистов не допускают до таких вещей).
Более того, специалисту по информатике было бы интересно узнать и наихудшее время при тасовании колоды. Анализ наихудшего случая позволяет нам получить четкие гарантии, что процесс в принципе конечен, что срок исполнения задачи не будет сорван.
Таким образом, до конца этой главы, да и, пожалуй, всей книги мы будем обсуждать действие алгоритмов в наихудших случаях, если не указано иное.
В программировании есть обозначение, придуманное специально для определения сценария алгоритма в наихудшем случае. Это прописная «О», или «О большое». За понятием «О большого» стоит одна небольшая хитрость, которая с первого взгляда не совсем очевидна. Суть в том, что «О большое» не столько выражает действие алгоритма в минутах и секундах, сколько может характеризовать тип взаимосвязи между размером задачи и временем, потраченным на ее решение. Поскольку «О большое» намеренно проливает свет на некоторые важные детали, перед нами появляется схема разделения задач на различные широкие категории.