Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - [6]
Как записывается «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).
• 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, после рассмотрения еще нескольких алгоритмов. А пока перечислим основные результаты:
• Скорость алгоритмов измеряется не в секундах, а в темпе роста количества операций.
• По сути формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.
