«О» большое — простое объяснение с картинками

1
5516
views

Бью Карнес — разработчик, ведущий YouTube-канал сайта freeCodeCamp.org, — в своей статье «Big O Notation — Simply explained with illustrations and video» попытался простыми словами объяснить нотацию большого «О».

"О" большое

Нотация «О» большое используется для выражения скорости алгоритма. Это важно при оценке как чужих алгоритмов, так и своих собственных. В этой статье я объясню, что такое «О» большое, а также приведу список наиболее часто встречающихся значений большого «О» и соответствующих этим значениям алгоритмов.

"О" большое.
«О» большое.
Почти все иллюстрации в этой статье авторства Адитьи Бхаргавы, автора книги «Грокаем алгоритмы».

Время работы алгоритмов растет с разной скоростью

У моего сына Иуды есть много игрушек. Их просто миллиард! Даже удивительно, как быстро ребенок может собрать такое количество игрушек, если он первый внук для обеих ветвей семейного древа.

В общем, у Иуды проблема. Когда к нему приходят друзья и хотят поиграть с какой-то определенной игрушкой, ее поиски могут занять целую вечность. Поэтому ему нужен алгоритм поиска, который помог бы найти нужную игрушку как можно быстрее. Он пытается выбрать между двумя разными алгоритмами: простым и двоичным.

Выбранный алгоритм должен быть и точным, и быстрым. С одной стороны, двоичный поиск быстрее. А у Иуды зачастую бывает лишь 30 секунд на поиски — пока его другу не станет слишком скучно искать игрушку. С другой стороны, алгоритм простого поиска легче написать, и шансы сделать что-то неверно гораздо меньше. Ведь если друг найдет баги в его коде, это будет очень огорчительно! Чтобы подойти к делу с максимальной точностью, Иуда решает засечь время, за которое каждый из алгоритмов справится со списком из ста игрушек.

Давайте предположим, что проверка одной игрушки занимает 1мс. Если Иуде придется проверить все 100 игрушек путем простого поиска, это займет 100мс. С другой стороны, применяя двоичный поиск, нужно проверить всего 7 игрушек (log2 100 это примерно 7, мы здесь не будем вдаваться в точную математику), а значит, на это уйдет 7мс.

Но на самом деле в списке миллиард игрушек. Сколько времени будет работать алгоритм простого поиска, обрабатывая такой список? А сколько времени понадобится алгоритму двоичного поиска?

Время работы простого и двоичного поиска

Время работы простого и двоичного поиска со списком из 100 элементов

Иуда запускает двоичный поиск со списком из 1 млрд. игрушек и на работу этого алгоритма уходит 30мс (log2 1000000000 примерно равен 30). «32мс! — думает он. — Сколько же времени понадобится при простом поиске? Двоичный поиск примерно в 15 раз быстрее простого, ведь алгоритму простого поиска понадобилось 100мс на список из 100 элементов, а алгоритму двоичного поиска — только 7мс. Значит, простой поиск со списком из 1 млрд. элементов займет 30мс*15 = 450мс, верно? Это намного меньше 30 секунд, за которые мой друг успеет устать». И Иуда решает воспользоваться алгоритмом простого поиска. Но был ли это правильный выбор?

Нет. Оказалось, что Иуда ошибся и, возможно, потерял своего друга навсегда. Время работы алгоритма простого поиска со списком из 1 млрд. элементов это не 450мс, а 1млрд. миллисекунд, т. е., 11 дней! Дело в том, что время работы двоичного и простого поиска возрастает не одинаково.

Как возрастает время работы алгоритмов

Время работы растет с разной скоростью! По мере увеличения количества элементов время работы двоичного поиска будет понемногу расти, но при этом время работы простого поиска возрастает очень сильно. То есть, когда число элементов в списке возрастает, двоичный поиск внезапно становится намного быстрее простого.

Так что Иуда ошибся, предполагая, что двоичный поиск всегда в 15 раз быстрее простого. Если брать список с 1 миллиардом элементов, двоичный поиск будет уже примерно в 33 миллиона раз быстрее простого.

Вот поэтому очень важно знать, с какой скоростью возрастает время работы алгоритма в зависимости от размера списка. И здесь выходит на сцену «О» большое.

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

Где же, собственно, время? Где секунды? Здесь их нет. «О» большое не сообщает вам скорость в секундах. Эта нотация позволяет вам сравнивать количество необходимых операций. Она говорит вам о том, как быстро возрастает скорость работы алгоритма.

Давайте рассмотрим еще один пример. Двоичному поиску для проверки списка из n элементов нужно осуществить log n операций. Каково время работы алгоритма, записанное в нотации «О» большого? O(log n). В общем, принцип записи следующий:

Нотация "О" большое

Эта запись сообщает вам количество операций, которое осуществит алгоритм. Называется все это нотацией ««О» большое», потому что перед количеством операций ставится заглавная буква «О».

«О» большое описывает количество операций при наихудшем сценарии

Поиск пользователей

Предположим, вы ищете пользователя в своей базе данных и при этом применяете алгоритм простого поиска. Вы знаете, что его скорость — O(n), то есть, в наихудшем случае вашему алгоритму придется проверить каждого пользователя в вашей базе данных. Но допустим, вы ищете пользователя с именем aardvark213, а он стоит первым в списке. Вашему алгоритму не придется проверять каждый элемент списка, потому что он найдет нужного пользователя с первой попытки. Итак, время, которое потребовалось алгоритму, это O(n) или O(1)? Ведь он нашел нужного пользователя с первой же попытки?

Время работы простого поиска в нотации «О» большое все равно O(n). В нашем случае алгоритм нашел искомое сразу. Это сценарий наилучшего случая. Но «О» большое описывает наихудший сценарий. То есть, можно сказать, что в наихудшем случае алгоритму придется по одному разу проверить каждого пользователя в базе данных, и на это уйдет время O(n). Это перестраховка: вы знаете, что скорость работы простого поиска никогда не будет меньше, чем O(n).

Самые распространенные варианты «О» большого

Если шутка не понятна, почитайте о задаче коммивояжера.

Вот пять вариантов «О» большого, которые встречаются чаще всего. Они отсортированы от самого быстрого к самому медленному:

  • O(log n) — логарифмическое время. Пример: двоичный поиск.
  • O(n) — линейное время. Пример: простой поиск.
  • O(n * log n). Пример: быстрый алгоритм сортировки, такой как quicksort (быстрая сортировка).
  • O(n2) — квадратичное время. Пример: медленный алгоритм сортировки, такой как сортировка выбором.
  • O(n!) — факториальное время. Пример: очень медленный алгоритм, такой как в задаче коммивояжера.

Визуализация разного времени в нотации «О» большого

Сетка из 16 ячеек

Предположим, вам нужно нарисовать сетку с 16 ячейками и вы можете выбрать для этого 5 разных алгоритмов (из списка выше).

Первый алгоритм займет O(log n) времени. Вы можете осуществлять 10 операций в секунду. Чтобы нарисовать сетку из 16 ячеек, при времени O(log n) вам понадобится осуществить 4 операции (log 16 с основанием 2 это 4). То есть, у вас на это уйдет 0,4с. Что, если нужно нарисовать 1024 ячеек? На это потребуется log 1024 = 10 операций, т. е., 1с. Это первый алгоритм.

Второй алгоритм медленнее, его время выполнения O(n). Чтобы нарисовать 16 ячеек, понадобится 16 операций, а чтобы нарисовать 1024 ячейки — 1024 операции. Сколько это в секундах?

На графиках вы можете увидеть скорость всех алгоритмов, от самого быстрого до самого медленного:

Графики, иллюстрирующие скорость алгоритмов

Есть и другие варианты времени выполнения алгоритмов, но эти встречаются чаще всего.

Конечно, это упрощение. На самом деле вы не сможете так точно конвертировать время, записанное при помощи «О» большого, в количество операций, но это хорошая прикидка.

Заключение

Вот основные вещи, которые нужно усвоить:

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

1 КОММЕНТАРИЙ

ОСТАВЬТЕ ОТВЕТ

Please enter your comment!
Please enter your name here