Обозначение Big O - просто объяснение с иллюстрациями и видео

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

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

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

В любом случае, у Джуды проблема. Когда его друзья приходят в гости и хотят поиграть с определенной игрушкой, их поиск может занять НАВСЕГДА. Поэтому он хочет создать алгоритм поиска, который поможет ему как можно быстрее найти конкретную игрушку. Он пытается выбрать между двумя различными алгоритмами поиска: простым поиском и двоичным поиском. (Не волнуйтесь, если вы не знакомы с этими алгоритмами.)

Выбранный алгоритм должен быть быстрым и правильным. С одной стороны, бинарный поиск быстрее. И у Джуды часто есть только 30 секунд, прежде чем его другу надоест искать игрушку. С другой стороны, простой алгоритм поиска легче написать, и вероятность появления ошибок меньше. Было бы неудобно, если бы его друг обнаружил ошибки в своем коде! Чтобы быть особенно осторожным, Джуда решает синхронизировать оба алгоритма со списком из 100 игрушек.

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

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

Джуда выполняет бинарный поиск с 1 миллиардом игрушек, и это занимает 30 мс (log2 1,000,000,000 - это примерно 30). «32 мс!» он думает. «Двоичный поиск примерно в 15 раз быстрее простого поиска, потому что простой поиск занимал 100 мс с 100 элементами, а двоичный поиск занимал 7 мс. Так что простой поиск займет 30 × 15 = 450 мс, верно? Меньше 30 секунд, чтобы моему другу стало скучно ». Иуда решает пойти простым поиском. Это правильный выбор?

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

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

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

Очень важно знать, как увеличивается время выполнения при увеличении размера списка. Вот где пригодится нотация Big O.

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

Где секунды? Их нет - Big O не сообщает вам скорость в секундах. Обозначение Big O позволяет сравнивать количество операций. Он говорит вам, насколько быстро растет алгоритм.

Приведем еще один пример. Двоичный поиск требует регистрации n операций для проверки списка размером n . Какое время работы в нотации Big O? Это O (log n ). В общем, нотация Big O записывается следующим образом.

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

Big O устанавливает время работы наихудшего случая

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

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

Некоторые общие времена выполнения Big O

Вот пять периодов выполнения Big O, с которыми вы будете часто сталкиваться, отсортированные от самого быстрого до самого медленного:

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

Визуализация различного времени выполнения Big O

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

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

Вот сколько времени потребуется, чтобы нарисовать сетку для остальных алгоритмов, от самого быстрого до самого медленного:

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

Это упрощение. В действительности вы не можете так точно преобразовать время выполнения Big O в ряд операций, но это хорошая оценка.

Вывод

Вот основные выводы:

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

А вот видео, которое охватывает многое из этой статьи и многое другое.

Надеюсь, эта статья прояснила вам нотацию Big O. Эта статья основана на уроке моего видеокурса от Manning Publications под названием «Алгоритмы в движении». Курс основан на замечательной книге Адита Бхаргавы «Алгоритмы поисковиков». Именно он нарисовал все забавные иллюстрации в этой статье.

Если вы лучше всего учитесь по книгам, получите книгу! Если вы лучше всего учитесь через видео, подумайте о покупке моего курса. Вы можете получить 39% скидку на мой курс, используя код 39carnes .