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

Другими словами, с увеличением количества элементов бинарный поиск занимает чуть больше времени. А простой поиск займет гораздо больше времени. Таким образом, с увеличением списка бинарный список внезапно начинает работать гораздо быстрее простого. Боб думал, что бинарный поиск работает в 15 раз быстрее простого, но это не так. Если список состоит из 1 миллиарда элементов, бинарный поиск работает приблизительно в 33 миллиона раз быстрее. Вот почему недостаточно знать, сколько времени должен работать алгоритм, — необходимо знать, как возрастает время выполнения с ростом размера списка. Здесь-то вам и пригодится «O-большое».

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

А теперь другой пример. Для проверки списка размером 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). И это дает определенные гарантии — вы знаете, что простой поиск никогда не будет работать медленнее