моментально; это лучший возможный случай. Однако «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), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.
• Скорость алгоритмов не измеряется в секундах.
• Время выполнения алгоритма описывается ростом
