Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава

моментально; это лучший возможный случай. Однако «O-большое» описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время O(n). И это дает определенные гарантии — вы знаете, что простой поиск никогда не будет работать медленнее O(n).

примечание

Наряду с временем худшего случая также полезно учитывать среднее время выполнения. Тема худшего и среднего времени выполнения обсуждается в главе 4.

Типичные примеры «O-большого»

Ниже перечислены пять разновидностей «O-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения:

• O(log n), или логарифмическое время. Пример: бинарный поиск.

• O(n), или линейное время. Пример: простой поиск.

• O(n* log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка — но об этом в главе 4).

• O(n2). Пример: медленные алгоритмы сортировки (сортировка выбором — см. главу 2).

• O(n!). Пример: очень медленные алгоритмы (задача о коммивояжере — о ней будет рассказано в следующем разделе).

Предположим, вы снова строите сетку из 16 квадратов, и вы можете выбрать для решения этой задачи один из 5 алгоритмов. При использовании первого алгоритма сетка будет построена за время O(log n). В секунду выполняются до 10 операций. С временем O(log n) для построения сетки из 16 квадратов потребуются 4 операции (log 16 равен 4). Итак, сетка будет построена за 0,4 секунды. А если бы было нужно построить 1024 квадрата? На это бы потребовалось log 1024 = 10 операций, или 1 секунда. Напомню, что эти числа получены при использовании первого алгоритма.

Второй алгоритм работает медленнее: за время O(n). Для построения 16 прямо­угольников потребуется 16 операций, а для построения 1024 прямоугольников — 1024 операции. Сколько это составит в секундах?

Ниже показано, сколько времени потребуется для построения сетки с остальными алгоритмами, от самого быстрого до самого медленного:

Существуют и другие варианты времени выполнения, но эти пять встречаются чаще всего.

Помните, что эта запись является упрощением. На практике «O-большое» не удается легко преобразовать в количество операций с такой точностью, но пока нам хватит и этого. Мы еще вернемся к «O-большому» в главе 4, после рассмотрения еще нескольких алгоритмов. А пока перечислим основные результаты:

• Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.

• По сути формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.

• Время выполнения алгоритмов выражается как «O-большое».

• Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.

Упражнения

Приведите время выполнения «O-большое» для каждого из следующих сценариев.

1.3 Известна фамилия, нужно найти номер в телефонной книге.

1.4 Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)

1.5 Нужно прочитать телефоны всех людей в телефонной книге.

1.6 Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ — скорее всего, он вас удивит!)

Задача о коммивояжере

Наверное, после прочтения предыдущего раздела вы подумали: «Уж мне-то точно не попадется алгоритм с временем O(n!)» Ошибаетесь, и я это сейчас докажу! Мы рассмотрим алгоритм с очень, очень плохим временем выполнения. Это известная задача из области теории вычислений, в которой время выполнения растет с просто ужасающей скоростью, и некоторые очень умные люди считают, что с этим ничего не поделать. Она называется задачей о коммивояжере.

Это коммивояжер.

Он должен объехать 5 городов.

Коммивояжер хочет побывать в каждом из 5 городов так, чтобы при этом проехать минимальное общее расстояние. Одно из возможных решений: нужно перебрать все возможные комбинации порядка объезда городов.

Все расстояния суммируются, после чего выбирается путь с кратчайшим расстоянием. Для 5 городов можно создать 120 перестановок, поэтому решение задачи для 5 городов потребует 120 операций. Для 6 городов количество операций увеличивается до 720 (существуют 720 возможных перестановок). А для 7 городов потребуется уже 5040 операций!

Количество операций стремительно растет

В общем случае для вычисления результата при n элементах потребуется n! (n-факториал) операций. А значит, время выполнения составит O(n!) (такое время называется факториальным). При любом сколько-нибудь серьезном размере списка количество операций будет просто огромным. Скажем, если вы попытаетесь решить задачу для 100+ городов, сделать это вовремя не удастся — Солнце погаснет раньше.

Какой ужасный алгоритм! Значит, коммивояжер должен найти другое решение, верно? Но у него ничего не получится. Это одна из знаменитых нерешенных задач в области теории вычислений. Для нее не существует известного быстрого алгоритма, и ученые считают, что найти более эффективный алгоритм для этой задачи в принципе невозможно. В лучшем случае для нее можно поискать приближенное решение; за подробностями обращайтесь к главе 10.

И последнее замечание: если у вас уже есть опыт программирования, почитайте о бинарных деревьях поиска! Эти структуры данных кратко описаны в последней главе.

Шпаргалка

• Бинарный поиск работает намного быстрее простого.

• Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.

• Скорость алгоритмов не измеряется в секундах.

• Время выполнения алгоритма описывается ростом