Честно говоря, когда я только начала изучать программирование, я долго прокрастинировала и не бралась за большое О. Эта статья для тех, кто испытывает тот же священный трепет.
Возможно, вам станет легче, если я скажу, что в этой теме все сводится к здравому смыслу, а по части математики тут нет ничего сложнее умножения. Но на всякий случай я все же добавлю пару иллюстраций. Картинки у меня довольно наивные, но лично мне они помогли запомнить материал.
Если бы передо мной поставили задачу выразить идею большого О или временной сложности кода как можно проще, я бы сделала это так:
- базовые операции — самые эффективные
- повторяющиеся операции (циклы) вызывают больше опасений по части эффективности
- производительность вложенных циклов наиболее сомнительная.
Вот честно: все сводится к этим основным положениям. Не слишком страшно, правда? Также есть целая категория вещей, о которых можно вообще не беспокоиться, они точно не ухудшат производительность кода. К ним относятся:
- основные математические действия — сложение и вычитание
- назначение переменных
- условия if/else
- объявление функции
- вызов функции
- изменение переменных.
Если попытаться как можно проще подытожить концепцию большого О, я бы сказала, что нас волнуют практически только циклы. Осознав это, я стала куда меньше бояться этой темы.
Примечание. В этой статье речь пойдет о самых основах. Я пишу для людей, которые считают нотацию большого О чем-то сродни древним ритуалам. Конечно, в этой теме куда больше нюансов, чем я разбираю здесь. Но если стоит выбор между ясностью и большим количеством подробностей, я выбираю ясность. Эта статья для новичков, нуждающихся в базовой и практической информации.
От редакции Techrocks. На тему большого О также можем предложить статью «Как работает «О» большое — объяснение на примере торта».
Чтобы получше разобраться в том, что собой представляет большое О, давайте рассмотрим примеры.
Предположим, в свободное время я занимаюсь охотой на мусор. (Прим. перев.: англ. scavenger hunt — «охота на мусор» — игра, участники которой должны найти и собрать за ограниченное количество времени определенные предметы).
Мои друзья дают мне задания, как простые, так и довольно сложные. Кстати, многие люди действительно так развлекаются! Такое хобби называется геокэшинг. Оно чем-то напоминает охоту за сокровищами. Но мои примеры в этой статье не дотягивают до геокэшинга, так что я назвала их охотой на мусор.
1. Постоянное время или О(1)
Джейми поставил передо мной задачу: взять шариковую ручку по определенному адресу на Каштановой улице. Мне нужно зайти всего в один дом, проще не придумаешь.
Это пример того, что мы называем «постоянным временем». Не важно, на что именно вы охотитесь: постучаться нужно всего в одну дверь. От предмета поиска сложность не зависит.
Производительность этого алгоритма очень хорошая. Можно сказать, самая оптимальная. Пример операции с постоянной временной сложностью — получение значения из объекта JavaScript.
const person={ name: "Ann", hobbies: ["drawing", "programming"], pet: "dog" } console.log(person.name)
Поскольку объекты JavaScript это примеры хэша, поиск значений в них очень производителен. Посещение дома по известному адресу без необходимости в собственно поиске — отличная аналогия. Что бы там ни было внутри, шаг получения элемента выполняется за постоянное время.
Именно поэтому такие структуры данных, как объекты/хэш, зачастую являются вашими лучшими друзьями в задачах на программирование.
Порой бывает очень полезно преобразовать массивы в формат объекта: это существенно улучшает производительность.
В нотации большого О это называется постоянным временем и записывается как О(1).
2. Логарифмическое время или O(log N)
Джейк дал мне задачку посложнее. Возле меня строят новый микрорайон. Дома уже стоят, но адресные таблички еще не развесили. Тем не менее, если подойти к дому, можно увидеть его номер возле звонка у входной двери. Моя задача — найти дом № 22.
Я совершенно не хочу подходить к каждому дому, чтобы увидеть его номер. Джейк еще сказал, что дома пронумерованы последовательно: чем дальше по улице, тем числа больше.
Я не знаю, с какого номера начинается и на каком кончается нумерация, потому что улица изгибается. Тем не менее, я могу подойти к дому посередине видимой части улицы и посмотреть его номер. В зависимости от того, будет номер больше или меньше 22, я смогу отбросить ту или иную половину домов.
Дом посередине, как оказалось, имеет номер 26. Значит, номера домов справа от него точно больше 22. Поэтому я могу вычеркнуть из списка для обхода и дом № 26, и все дома справа.
Дальше я могла бы просто отсчитать нужное количество домов влево. Но есть одно «но». Улица не полностью застроена, на некоторых участках домов нет. И я не знаю, присвоены ли этим участкам номера (может, там позже дома построят). Так что просто посчитать «по головам» не получится.
Я решаю снова воспользоваться своим приемом и из оставшихся домов выбрать дом посередине. Таким образом я по крайней мере смогу снова переполовинить список.
Мне повезло, это оказался искомый дом № 22. Как видите, мой алгоритм поиска дал хороший результат. Мне пришлось подойти всего к двум домам, хотя на видимой части улицы их было семь. Подход к каждому из этих домов уменьшал список оставшихся на половину.
Когда на каждой итерации итоговый набор разрезается надвое, производительность такого подхода называется логарифмической. После постоянного времени это наилучший результат из возможных. Даже если в списке семь элементов, операций нужно проделать всего две.
Если вы не очень хорошо помните, что такое логарифмы, ничего страшного. Все, что вам нужно знать, это что логарифмическая производительность алгоритма это отлично, потому что результирующий список существенно уменьшается на каждой итерации.
В нотации большого О мы записываем логарифмическую производительность как O(log n). Если боитесь, что не запомните эту запись, на собеседовании можно просто говорить «логарифмическое время». Все, что вам нужно знать, это что при логарифмической производительности каждый шаг разрезает результаты пополам. Зная это, вы легко «узнаете» сложность своего алгоритма, если он будет работать именно таким образом.
Примечание. Мой поиск дома № 22 — это алгоритм двоичного поиска. Хорошая штука, правда? Просто берешь серединное значение снова и снова. Этот алгоритм — прекрасный выбор для случаев, когда вы знаете, что ваш список как-то упорядочен.
От редакции Techrocks. На тему алгоритмов и нотации большого О есть отличная статья «Разбираемся в алгоритмах и структурах данных. Доступно и понятно». Практическое применение алгоритма бинарного поиска рассмотрено в статье «Дебаггинг с использованием git bisect».
3. Линейное время или O(n)
Моя подруга Джесс, услышав, как я в поте лица охочусь на мусор, решила меня «пожалеть». К счастью, как раз был Хеллоуин. Джесс придумала мне задание: просто получить по конфете в каждом доме на Сикоморной улице.
На этой несколько запутанной иллюстрации видно, насколько моя задача сложнее по сравнению с предыдущей.
Это то, что в нотации большого О мы называем «линейным временем» (или циклом, или простым умножением). Моя задача умножается на количество домов. Если улица достаточно длинная, мне может понадобиться обойти до 50 домов. Затраченные усилия возрастают линейно в привязке к количеству домов на улице.
Что касается большого О, линейное время — во многих случаях довольно хорошая производительность алгоритма. Да, она не настолько хорошая, как у алгоритмов с постоянным и логарифмическим временем. Но обычно задачи на программирование, которые вам предлагают решить на собеседовании, достаточно сложные, и скорее всего там будут задействованы циклы.
Линейное время в нотации большого О записывается как O(n), где n — множитель, количество итераций цикла, которые нужно пройти.
4. Квадратичное и кубическое время
Мой последний приятель, Эндрю, настоящий дьявол. Он придумал самое сложное задание. Мне нужно обойти каждый дом на улице и проверить, найду ли я вещь из каждого отдельного дома во всех остальных.
Если на улице пять домов, у меня получается 25 отдельных задач, потому что нужно поискать пять вещей в каждом из пяти домов. То есть у меня 5 х 5 задач или 5^2. Это то, что мы называем квадратичным временем.
В программировании это означает одно: вложенные циклы! Каждый вложенный цикл добавляет единицу к показателю степени. Если бы Эндрю сказал обойти не одну улицу, то это было бы уже улицы х дома х вещи. И это было бы кубическое время или O(n^3). В реальной жизни мы сталкиваемся с ним, когда увеличиваем вложенность цикла.
Мой пример еще довольно реальный (я могу проделать 25 итераций), но в программировании речь может идти о куда больших числах. Посмотрите, как раздувается количество задач:
| Базовое число | задачи^2 | задачи^3 | задачи^4 |
|---|---|---|---|
| 100 | 10000 | 1000000 | 100000000 |
| 1000 | 1000000 | 1000000000 | 1000000000000 |
| 10000 | 10000000000 | 1000000000000000 | 100000000000000000000 |
| 100000 | 1000000000000 | 1000000000000000000 | 1000000000000000000000000 |
Это, пожалуй, самое важное, что нужно понять и запомнить по части производительности алгоритмов, потому что такой прирост количества задач имеет большое значение.
Легко заметить, что при базовом числе 100 и неосторожном обращении с циклами можно быстро получить количество операций большее, чем при базовом миллионе. И наоборот, при наборе данных с миллионом записей программа может выполнять меньше работы, чем при ста записях — все зависит от того, насколько аккуратно мы обращаемся со вложенными циклами.
В задачах на программирование самое сложное и интересное — попытаться обойтись простым циклом, без вложенного, или даже вообще без цикла.
Ситуации, когда количество вычислений удваивается при добавлении каждого нового элемента в набор данных, в нотации большого О описываются как O(2^n). Это экспоненциальное время.
5. Пример оценки решения задачи
Допустим, перед нами стоит следующая задача.
Дан массив уникальных целых чисел и целевое число. Определите, есть ли в массиве любые два числа, в сумме дающие целевое число. Если такие числа есть, верните их позиции в массиве. Использовать дважды число на одной позиции нельзя. (То есть массив [4, 2] может составить целевое число 6, а массив [3] — не может, потому что нельзя дважды использовать число на позиции [0].
Пример 1. Дан массив [1, 2, 3, 4, 5, 6] и целевое число 10. Вернуть нужно [3, 5], потому что на 3-й позиции есть число 4, а на 5-й — число 6, в сумме эти числа дают 10.
Пример 2. Дан массив [1, 2, 4] и целевое число 50. Вернуть нужно false, потому что условие не соблюдено.
Это немного измененная задача с Leetcode. К ней прилагался дополнительный вопрос: «Сможете ли вы достичь временной сложности ниже, чем O(n^2)?». Вопрос, собственно, намекает, что это возможно. Но для программиста-новичка очевидный способ решения этой задачи может быть примерно следующим (запустить этот код можно здесь):
Как видите, здесь у нас экспоненциальная логика и довольно много вызовов в методе.
Я уже говорила, что всегда стараюсь использовать преимущества постоянного и линейного времени. Поэтому и в данном случае попробую переписать функцию так, чтобы получить лучшее большое О.
Хэши — отличное решение для такого рода задач. Поэтому при итерации списка я создам объект JavaScript. В каждой паре ключ-значение ключом будет число, которое нужно добавить к элементу, чтобы получить целевое число, а значением — индекс самого элемента.
Пример: дано целевое число 8 и список [1,2,3,4,9,6]. Мой объект JS будет выглядеть так: { // Первый элемент массива - 1, чтобы в сумме получить 8, вторым слагаемым должно быть число 7. Сам элемент 1 стоит под индексом 0. 7: 0, // Второй элемент массива - 2. Чтобы получить в сумме 8, надо добавить 6. Индекс двойки - 1. // И так далее. 6: 1, 5: 2, 4: 3, 6: 5 }
С таким объектом мне не придется создавать вложенный цикл. Я могу сделать обычный цикл (т. е. сложность будет линейной) и проверять, является ли текущий элемент списка ключом в объекте JavaScript. Если да, я нашла второе слагаемое. Я сохранила индекс, по которому располагалось первое слагаемое, в качестве значения ключа, так что он у меня уже есть. Далее я могу просто вернуть индекс текущего элемента во втором цикле. Вы можете поиграть с этим кодом здесь.
Я использовала те же тест-кейсы и, как видите, получила те же результаты. Но со вложенным циклом наихудшая производительность была > 200 операций, а без вложенного — всего 30! Это потрясающе. И когда вы привыкнете обдумывать производительность при решении задач, вам будет несложно избавляться от вложенных циклов.
Визуализация изученного
Увидеть разницу в производительности алгоритмов помогают графики:
Примечание
Вероятно, вы пытались определить временную сложность алгоритма в нашей задаче и, возможно, предположили, что это O(2(n)). Ну то есть один цикл дает сложность O(n), а мы должны сперва в одном цикле создать объект JavaScript, а затем в другом цикле обработать список и проверить, есть ли числа, в сумме дающие целевое число.
Но припомните: в начале статьи я говорила, что все, о чем стоит беспокоиться, это циклы. Нас волнуют только наибольшие разбросы количества операций. Что это означает?
- Если у вас в программе есть цикл с производительностью O(n), а далее в коде встречается еще один цикл, только вложенный, с производительностью O(n^2), мы считаем, что для вашей программы большое О — просто O(n^2). Большее оставляем, меньшее отбрасываем.
- Если у вас есть вложенный цикл с производительностью O(n^2), а дальше встречается цикл с большей вложенностью и производительностью O(n^3), то в целом программа имеет кубическую временную сложность.
Если подумать, это довольно логично. Практически в любой программе у вас будут операции со временной сложностью O(1), но программа в целом крайне редко имеет постоянную сложность. Даже один цикл в программе изменит сложность в худшую сторону.
Заключение
Есть и другие варианты большого О, но эти мне попадаются наиболее часто. К тому же, в задачах на программирование начинающий разработчик тоже скорее всего столкнется именно с ними.
Даже если вы не слишком хорошо разбираетесь в математических концепциях, просто запомните, что при оценке производительности кода внимание нужно обращать на циклы. Это поможет вам писать более эффективный код.
Перевод статьи «Big O notation basics made dead simple».
Запись Большое О для самых маленьких впервые появилась Techrocks.