А теперь другой пример. Для проверки списка размером n бинарному поиску потребуется log n операций. Как будет выглядеть «O-большое»? O(log n). В общем случае «O-большое» выглядит так:
Как записывается «O-большое»
Такая запись сообщает количество операций, которые придется выполнить алгоритму. Она называется «O-большое», потому что перед количеством операций ставится символ «O» (а большое — потому что в верхнем регистре).
Теперь рассмотрим несколько примеров. Попробуйте самостоятельно оценить время выполнения этих алгоритмов.
Наглядное представление «O-большое»
Чтобы повторить следующий практический пример, достаточно иметь несколько листков бумаги и карандаш. Допустим, вы должны построить сетку из 16 квадратов.
Как должен выглядеть хороший алгоритм для построения этой сетки?
Алгоритм 1
Как вариант можно нарисовать 16 квадратов, по одному за раз. Напоминаю: «O-большое» подсчитывает количество операций. В данном примере рисование квадрата считается одной операцией. Нужно нарисовать 16 квадратов. Сколько операций по рисованию одного квадрата придется выполнить?
Сетка рисуется по одному квадрату
Чтобы нарисовать 16 квадратов, потребуется 16 шагов. Как выглядит время выполнения этого алгоритма?
Алгоритм 2
А теперь попробуем иначе. Сложите лист пополам.
На этот раз операцией считается сложение листка. Получается, что одна операция создает сразу два прямоугольника!
Сложите бумагу еще раз, а потом еще и еще.
Разверните листок после четырех сложений — получилась замечательная сетка! Каждое сложение удваивает количество прямоугольников. За 4 операции вы создали 16 прямоугольников!
Построение сетки за 4 сложения
При каждом складывании количество прямоугольников увеличивается вдвое, так что 16 прямоугольников строятся за 4 шага. Как записать время выполнения этого алгоритма? Напишите время выполнения обоих алгоритмов, прежде чем двигаться дальше.
Ответы: алгоритм 1 выполняется за время O(n), а алгоритм 2 — за время O(log n).
«O-большое» определяет время выполнения в худшем случае
Предположим, вы используете простой поиск для поиска фамилии в телефонной книге. Вы знаете, что простой поиск выполняется за время O(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начинается на букву «А» и этот человек стоит на самом первом месте в вашей телефонной книге. В общем, вам не пришлось просматривать все записи — вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время O(n)? А может, он занял время O(1), потому что результат был получен с первой попытки?
Простой поиск все равно выполняется за время O(n). Просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако «O-большое» описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время O(n). И это дает определенные гарантии — вы знаете, что простой поиск никогда не будет работать медленнее O(n).
примечание
Наряду с временем худшего случая также полезно учитывать среднее время выполнения. Тема худшего и среднего времени выполнения обсуждается в главе 4.
Типичные примеры «O-большого»
Ниже перечислены пять разновидностей «O-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения:
• O(log n), или логарифмическое время. Пример: бинарный поиск.
• O(n), или линейное время. Пример: простой поиск.
• O(n* log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка — но об этом в главе 4).
• O(n2). Пример: медленные алгоритмы сортировки (сортировка выбором — см. главу 2).