Перевод статьи «How Big O Notation Works – Explained with Cake».
Нотация «О» большое используется в информатике для определения верхнего предела алгоритма. Главным образом это нужно для установления максимального времени работы алгоритма в зависимости от размера входящих данных, но также может использоваться для определения уровня использования памяти.
В этой статье мы рассмотрим самые типичные варианты «О» большого, а для иллюстрации концепции используем примеры с тортами. Итак, представьте, что вы устраиваете вечеринку по случаю дня рождения и вам нужно определить (ориентируясь на количество приглашенных), сколько тортиков испечь.
O(1) — постоянное время
Если мы говорим о постоянном времени, то совершенно все равно, сколько людей придет на ваш день рождения: все равно вы печете только один торт. Таким образом время, которое вы тратите на приготовление торта, остается неизменным.
Обратите внимание, что нотация «О» большое не определяет, сколько конкретно времени будет затрачено. Может, на приготовление торта уйдет один час, а может и четыре. Постоянное время означает лишь то, что время не зависит от числа гостей.
Если брать пример из жизни, то постоянная временная сложность будет у обращения к элементу массива по индексу. Скорость, с которой вы получите нужный элемент, одинакова для массива из 10 элементов и массива из миллиона элементов.
O(log n) — логарифмическое время
Если мы говорим о логарифмическом времени применительно к тортам, то это ситуация, когда вы при помощи тортов поощряете гостей приходить пораньше.
Скажем, гость, пришедший первым, получает целый торт, а следующие два гостя получают один торт на двоих. Дальше один торт приходится на четверых гостей и так далее.
Таким образом, если на вашу вечеринку приходит 1 человек, то вам нужен 1 торт. Вечеринка на 2-3 человека потребует 2 торта. Если вы ждете 4-7 человек, вам нужно печь 3 торта, а если 8-15 человек, то 4 торта. В общем, для вечеринки на n человек потребуется log2(n) тортов.
Самый обыденный «жизненный» пример операции с логарифмической временной сложностью — двоичный поиск в упорядоченном массиве.
Этот алгоритм ищет середину массива и смотрит, является это серединное значение больше или меньше искомого. Поскольку список упорядоченный, алгоритм может понять, в какой половине массива нужно искать дальше. Для этой половины процедура поиска повторяется.
Таким образом, если у нас массив из 16 элементов, первая итерация сужает поиск до 8 элементов, вторая — до 4, третья — до 2, а четвертая — до 1. То есть, всего у нас будет максимум 4 итерации или log2(16).
O(n) — линейное время
Давайте теперь разберем пример с линейным временем. В этом случае каждый гость получает собственный торт. Если на вечеринку приходит n людей, вам нужно испечь n тортов. Поэтому время приготовления зависит от количества гостей.
Напоминаем, что нотация «О» большое не определяет, как долго печется торт (может, 1 час, а может и 4). Она определяет, что в данном случае время выпечки возрастает в линейной зависимости от числа гостей.
Жизненный пример операции с линейной временной сложностью — простейший алгоритм поиска элемента в массиве. Если в массиве всего 10 элементов, в наихудшем случае для поиска нужного придется перебрать все. Если в массиве миллион элементов, то и перебрать придется миллион.
Разумеется, можно (случайно) найти нужный элемент раньше, но нотация «О» большое определяет максимальное количество времени, которое понадобится для работы алгоритма (т. е. наихудший вариант).
O(n^2) — квадратичное время
Разберем теперь пример квадратичного времени. При таком варианте каждый гость опять же получает свой собственный торт. Но теперь на каждом торте глазурью написаны имена всех гостей.
Если на вечеринку приходит один гость, он получает торт со своим именем. Для вечеринки с двумя гостями нужно два торта, а на каждом еще надо надписать по два имени (то есть в общем 4 надписи). Придут 3 гостя — понадобится 3 торта и 9 надписей.
Итого, для вечеринки на n человек вам придется сделать n*n надписей с именами. Время, которое понадобится на изготовление тортов и нанесение надписей, зависит от числа гостей в квадрате.
Реальный пример операции с квадратичной временной сложностью — простейший поиск дубликатов в массиве. При таком сценарии вам нужно перебрать все элементы в массиве, и для каждого из них перебрать массив еще раз (в поиске дубликатов).
Если в массиве 10 элементов, во внешнем цикле будет 10 итераций, а для каждой из них — еще 10 итераций вложенного цикла, то есть в сумме будет 100 итераций. Если в массиве миллион элементов, итераций будет 1000 миллиардов.
Есть более общий случай квадратичного времени — полиномиальное время. Квадратичное время в нотации «О» большое записывается как O(n^2) и описывает зависимость от n в квадрате (второй степени). А полиномиальное время описывает зависимость от n в степени c — O(n^c).
O(n!) — факториальное время
Если рассматривать факториальное время в разрезе вечеринки, здесь гости участвуют в игре в петанк, а победитель забирает торт домой.
Тут, правда, есть небольшая проблема: игрок, бросающий шар первым, находится в невыгодной позиции. Чтобы уравнять шансы, проводится много раундов с перестановкой игроков, чтобы каждый по разу побыл первым. Все эти перестановки записываются на торте (глазурью, конечно).
Это означает, что если на вечеринку пришло 2 человека, будет 2 игры (сначала первым будет один гость, потом другой). Если гостей будет 3, придется провести 6 игр. Допустим, гостей зовут Анна, Брайан и Крис. Варианты перестановок в таком случае — АБК, АКБ, БАК, БКА, КАБ, КБА.
В общем, на вечеринке на n гостей придется провести n! игр. Время, которое потребуется на нанесение соответствующих записей перестановок на торт, зависит от факториала числа n.
Факториал n вычисляется перемножением всех целых чисел от n до 1. Формула — n * (n - 1) * (n - 2) … * 2 * 1. Если на вечеринку пришли 3 человека, это 3 * 2 * 1, то есть 6.
Жизненный пример операций с факториальной временной сложностью — любой случай, где нужно анализировать список перестановок. Например, задача коммивояжера.
Заключение
Надеемся, примеры с тортами упростили для вас понимание нотации «О» большое. Представленный ниже график — хорошая «напоминалка», наглядно демонстрирующая скорости алгоритмов в сравнении.
Различных вариантов «О» большого довольно много. Есть, например, O(n log n) и O(c^n), но все они следуют одному шаблону. Список можно посмотреть здесь.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]
