Более того, специалисту по информатике было бы интересно узнать и наихудшее время при тасовании колоды. Анализ наихудшего случая позволяет нам получить четкие гарантии, что процесс в принципе конечен, что срок исполнения задачи не будет сорван.
Таким образом, до конца этой главы, да и, пожалуй, всей книги мы будем обсуждать действие алгоритмов в наихудших случаях, если не указано иное.
В программировании есть обозначение, придуманное специально для определения сценария алгоритма в наихудшем случае. Это прописная «О», или «О большое». За понятием «О большого» стоит одна небольшая хитрость, которая с первого взгляда не совсем очевидна. Суть в том, что «О большое» не столько выражает действие алгоритма в минутах и секундах, сколько может характеризовать тип взаимосвязи между размером задачи и временем, потраченным на ее решение. Поскольку «О большое» намеренно проливает свет на некоторые важные детали, перед нами появляется схема разделения задач на различные широкие категории.
Представьте, что вы организуете ужин с друзьями, количество которых мы обозначим как n. Время, которое вам необходимо на уборку дома до их прихода, не зависит от n.
Это самая простая категория задач, которая называется «О большое от единицы» (обозначается как «О(1)») и также известна как временнáя константа. Примечательно, что для «О большого» абсолютно не важно, сколько времени у вас на самом деле занимает уборка. Главное – что временной промежуток всегда один и тот же, вне зависимости от списка гостей. От вас требуется выполнить одну и ту же работу, не важно, пригласили вы одного друга, десять, сто или любое другое количество.
Теперь время, которое займет передача жаркого вокруг стола, мы обозначим как «О большое от n» (письменно – «O(n)»). Это понятие также имеет другое название – «линейное время». Если количество гостей увеличивается в два раза, то же происходит и с линейным временем. И снова, для «О большого» безразлично, какое количество блюд вы подаете или, например, сколько раз гости попросят добавки. В каждом случае время линейно зависит от количества приглашенных гостей и график зависимости времени от количества гостей будет представлять собой прямую. Более того, существование любых линейно-временных факторов – в случае «О большого» – будет перекрывать все факторы временных констант.
Другими словами, «передача жаркого вокруг стола» и «передача жаркого вокруг стола после трехмесячной перепланировки вашей столовой» – для программиста, по сути, абсолютно равнозначные величины.
Если вам это кажется безумным, подумайте о том, что компьютеры работают с величинами n, которые могут исчисляться тысячами, миллионами или миллиардами. Иначе говоря, программисты мыслят очень, очень большими объемами данных. Если у вас миллион гостей, то по сравнению с единичной передачей блюда вокруг стола весь процесс перепланировки дома покажется вам ничтожным.
А что если каждый прибывающий гость будет обнимать остальных при приветствии? Ваш первый гость обнимет только вас, второму придется обнять уже двоих, третий гость обнимет уже троих. Сколько объятий случится за вечер?
Эта задача перейдет уже в разряд «О большое от n в квадрате» («О(n2)»), или квадратичного времени. Опять же для нас важны только общие черты связей между переменной n и временем. Не существует формулы O(2n2) для двух объятий на каждого или формулы O(n2 + n) для объятий и передачи блюда. Таким образом, O(n2) охватывает все процессы.
Вот здесь становится трудно, потому что появляется экспоненциальное время, которое рассчитывается по формуле O(2n), когда каждый дополнительный гость удваивает вашу работу. Еще сложней все обстоит с факториальным временем, определяемым по формуле O(n!). Это категория задач столь бесчеловечно трудных, что программисты упоминают их только в шутку (как мы, говоря, например, о сортировке колоды до победного конца) или когда им на самом деле очень-очень хотелось бы пошутить.
Квадраты: «пузырьковая» сортировка и сортировка методом вставок
Когда Обама, находясь еще в статусе сенатора, в 2007 году посетил офис Google, глава компании Эрик Шмидт в шутку начал общение в манере собеседования и задал вопрос, как лучше отсортировать миллион 32-битных целых чисел. Обама саркастически улыбнулся и без промедления ответил: «Думаю, пузырьковая сортировка здесь не подойдет». Толпа инженеров Google разразилась аплодисментами.
«Он меня поразил пузырьковой сортировкой», – вспоминал один из них позднее. Обама был прав, что сразу отверг «этот алгоритм, который стал чем-то вроде боксерской груши для студентов-программистов: он достаточно прост, интуитивно понятен и весьма эффективен».
Представьте, что вы хотите расставить в алфавитном порядке одну из ваших книжных коллекций. Самым естественным подходом в этом случае было бы просмотреть книги на полке, чтобы выявить неупорядоченные пары (Уоллес, который «стоит» перед Пинчоном, к примеру) и поменять их местами. Поставьте Пинчона перед Уоллесом, затем продолжите осмотр полки, каждый раз возвращаясь к ее началу. Когда вы просмотрите всю полку и больше не найдете пар, стоящих в неправильном порядке, ваша задача будет выполнена.
Это и есть пузырьковая сортировка, и она погружает нас в квадратичное время. Есть n неупорядоченных книг, и в результате каждого осмотра полки вы можете переставить только одну книгу на другое место (решаем проблемы по мере поступления). То есть в худшем случае, если все книги на полке стоят в обратном порядке, то по меньшей мере одну книгу придется переставить на другое место n раз. Таким образом, мы получаем максимум n осмотров полки, на которой стоит n книг, то есть O(n2) в худшем случае
[8]. Но это не слишком ужасно по одной причине: это в миллион раз лучше, чем наша идея сортировки «до победного конца» по формуле O(n!) из предыдущего кейса. И все же вместе с тем этот квадратный корень может очень скоро вас напугать. Например, квадратный корень означает, что сортировка пяти книжных полок займет не в пять раз больше времени, чем сортировка одной, а в 25 раз больше.
В принципе вы можете взять и другой курс – вытащить все книги из шкафа и поставить их в правильном порядке одну за другой. Вы поставите первую книгу в середине полки, затем возьмете вторую, сравните ее с первой и поставите ее либо справа, либо слева от первой книги. Взяв третью, вы просмотрите книги, которые уже стоят на полке, слева направо и определите для нее нужное место. Повторяя этот процесс, вы постепенно расставите все книги на полке в нужном порядке, и ваша миссия будет выполнена.
