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