Основы нотации Big O стали мертвецки простыми


Краткая беседа о Big O

Честно говоря, когда я впервые занялся программированием, я довольно долго откладывал изучение Big O из-за страха, и эта статья предназначена для всех, кто чувствует себя так же. Не знаю, поможет ли мне сказать, что большинство из этого — здравый смысл, а математика не сложнее умножения. Но на всякий случай я добавлю несколько наглядных примеров, чтобы сделать это как можно менее неприятным. Графика очень глупая, но, честно говоря, это помогает мне запоминать вещи.

Если бы я хотел дать вам самую простую версию идеи, лежащей в основе нотации Big O, или временной сложности выполнения вашего кода, это было бы примерно так:

  • основные операции являются наиболее эффективными
  • повторяющиеся операции (циклы) могут вызывать больше опасений в плане эффективности
  • вложенные циклы — одна из самых больших проблем для эффективности.

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

  • базовая математика, сложение и вычитание
  • присвоение переменных
  • условия if/else
  • объявление функции
  • вызов функции (по номинальному значению)
  • изменение переменных

Если бы мне пришлось изложить концепцию Big O в самых простых терминах, которые только можно себе представить, то циклы — это практически все, о чем мы беспокоимся. Я знаю, что когда я понял это, я почувствовал себя гораздо менее запуганным.

💡Перед тем, как мы начнем: Это абсолютные основы, для тех, кто думает, что нотация Big O звучит как архаичный ритуал. Существует больше нюансов и больше описаний, чем я включил сюда. Всякий раз, когда есть возможность выбрать ясность по сравнению с большей детализацией, я выбираю ясность. Этот пост предназначен для тех, кто только начал программировать, и кому нужна базовая, действенная информация. Это часть большой серии, которую я пишу о живых интервью по кодингу, так что почитайте и ее 🤓.


Чтобы объяснить некоторые из них, давайте представим, что в свободное время я люблю охотиться на мусор. Мои друзья устанавливают правила для этих охот, и некоторые из них менее сложны, чем другие. (На заметку: некоторые люди действительно так делают! Существует хобби под названием «геокешинг», которое очень похоже на поиск сокровищ в реальной жизни. Если вам интересно, вы можете прочитать об этом здесь. Мои примеры слишком глупы, чтобы соответствовать настоящему геокешингу, поэтому я буду использовать термин «охота на мусор»).

Часть I: Постоянное время или O(1)

🏴☠️ Джейми отправляет меня на поиски сокровищ, чтобы найти ручку по определенному адресу на Каштановой улице. У меня один адрес, поэтому мне нужно пойти только в один дом, проще простого.

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

const person = {
  name: "Ann", 
  hobbies: ["drawing", "programming"], 
  pet: "dog"
}

console.log(person.name)
Вход в полноэкранный режим Выход из полноэкранного режима

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

По этой причине структуры данных object/hash часто являются вашим другом в кодовых задачах.

Иногда перевод массивов в объектный формат может быть очень полезен для хорошей производительности в таких задачах. Мы называем это постоянным временем O(1), в нотации Big O.

Часть 2: Логарифмическое время, или O(log N)

🎁 Мой друг Джейк поставил передо мной более сложную задачу. Недалеко от меня строится новый микрорайон, но они не добавили видимых уличных знаков. Однако, если я подойду к домам, они напишут адрес на балках у входной двери.

Мне не очень хочется подходить к каждому дому отдельно, но, подумав об этом, я поняла, что Джейк рассказал, что номера адресов домов увеличиваются по мере продвижения по улице.

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

Я вижу, что дом в центре — №26, поэтому все дома справа от него будут иметь номера домов, слишком высокие для того, что я ищу — №22. Поэтому я могу вычеркнуть дом, к которому я подошел, и все дома справа от него, потому что они будут иметь еще более высокие номера.

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

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

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

Мы называем производительность, когда вы каждый раз сокращаете набор результатов, логарифмической производительностью, и по прошествии постоянного времени (O(1)) она является настолько идеальной, насколько вы можете получить. Даже если у вас есть набор результатов из 7, операций, которые вы выполняете, может быть всего 2. Если вы не очень хорошо помните логарифмы из математики, это не страшно — все, что вам нужно знать, это то, что это ПРЕКРАСНАЯ производительность для алгоритма, потому что вы каждый раз значительно сокращаете набор результатов.

На языке Big O мы пишем логарифмическую производительность как O(log n). Если вы беспокоитесь о том, чтобы запомнить дескриптор Big O, просто назовите это «логарифмическое время» на собеседовании — это вполне нормально. А если все, что вам нужно знать, это то, что логарифмическое время означает, что с каждым проходом вы потенциально сокращаете свои результаты вдвое, то это довольно легко понять, когда вы это делаете.

В качестве примечания: мой пример с охотой за мусорщиками — это пример алгоритма двоичного поиска. Не так уж плохо, верно? Просто выбирайте из середины снова и снова. Это отличный алгоритм для использования, если вы знаете, что ваши результаты уже упорядочены.

Часть 3: Линейное время, или O(n)

🍬 Моя подруга Джесс, услышав, сколько работы я вложил в эти охоты за мусорщиками, сжалилась надо мной. К счастью для меня, это случилось 31 октября, и она поручает мне задание — пойти на хитрость или угощение! Моя задача — собрать по одной конфете из каждого дома на улице Сикамор.

На этом несколько нарочито беспорядочном графике вы можете увидеть, насколько это большая работа по сравнению с моим последним заданием.

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

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

Часть 4: Квадратичное и кубическое время

👿 Мой последний приятель, Эндрю, очень коварен и отправляет меня на самый трудный поиск сокровищ. Он отправляет меня на главную улицу и говорит, что для каждого дома на улице я должен найти предмет, дублирующийся в каждом доме.

Очень быстро у меня появляется 25 индивидуальных заданий, поскольку мне нужно найти пять предметов в каждом из пяти домов. Вы можете легко увидеть, что если мы переведем это в числа, то у меня будет 5 x 5 задач, или 5^2. Это то, что мы называем квадратичным временем.

В программировании это означает одно: вложенные циклы! Каждый вложенный слой добавляет экспоненту. Если бы мой друг сказал, что я хочу, чтобы ты сделал это для более чем одной улицы, математика стала бы чем-то вроде район x дома x предметы, и легко могла бы попасть в кубическое время, или O(n^3), часто представленное в третьем вложенном цикле в реальной жизни.

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

Базовое число Задачи ^ 2 Задачи ^ 3 Задачи ^ 4
100 10000 1000000 100000000
1000 1000000 1000000000 1000000000000
100000 10000000000 1000000000000000 100000000000000000000
1000000 1000000000000 1000000000000000000 1000000000000000000000000

Это, возможно, самая важная область, о которой я могу с вами поговорить. В моей работе она встречается чаще всего, а в программировании — чаще всего. Вы можете быстро понять, почему она становится важной.

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

Большинство тонких моментов, которые возникают у меня при решении кодовых задач, — это вопрос, могу ли я получить что-то от цикла к постоянному времени, а затем — могу ли я получить что-то от вложенного цикла к одному циклу. (То есть от кубического времени O(n^3) к квадратичному O(n^2))*.

У нас также есть более общее слово для обозначения ситуаций, когда экспонента будет в степени n: *экспоненциальное время (O(2^n)).

Часть 5: Как это может выглядеть

Допустим, мы получили следующую кодовую задачу.

Given an array of unique integers and a target number, determine if any two 
numbers in the array when added together would equal the target. If that 
condition is met, return the array position of the two numbers. You cannot 
reuse a number at a single index position (So array [4,2] could make
target number 6, but array [3] could not since it would require reusing the
array value at position array[0]).

Example: given array [1, 2, 3, 4, 5, 6] and target number 10, you would return 
an answer [3, 5] since at array[3] you have number 4, at array[5] you have 
number 6, and added together they make 10. 

Example: given array [1,2,4] and target number 50, you would return false 
because the condition can not be met. 
Войти в полноэкранный режим Выйти из полноэкранного режима

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

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

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

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

Example: given target number 8 and list [1,2,3,4,9,6] my JS object would 
look like this:
{
   // first array item is 1, we'd need to find a 7 to make 8, its at index 0
   7: 0, 
   // second array item is 2, we'd need to find a 6 to make 8, its at index 1
   // so on and so forth
   6: 1, 
   5: 2, 
   4: 3,
   6: 5
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Таким образом, этот объект означает, что мне не нужно делать вложенный цикл. Я могу сделать еще один обычный цикл (так что время линейное) и просто проверить, является ли текущий элемент списка одним из ключей для этого объекта Javascript. Если да, то я нашел подходящую пару, сумма которой является целевым числом. Я сохранил индекс, в котором находилось первое число, в качестве значения ключа, так что он у меня уже под рукой, а затем я могу просто вернуть индекс элемента списка, на котором я нахожусь, во втором цикле. Вы также можете поиграть с этим кодом здесь.

Я использовал те же тестовые примеры и, как видите, получил те же результаты. Но с моим подходом с вложенными циклами наихудшая производительность, которую мы видели, составляла > 200 операций, а без вложенных циклов — всего ТРИДЦАТЬ! Это довольно удивительно. И это было не так уж сложно, как только вы привыкнете думать таким образом, извлечь поведение вложенного цикла и найти другой способ.

Визуализация того, что мы узнали

Один из отличных способов наглядно показать, как это работает, — посмотреть на график производительности, я взял его с этого сайта.

Еще одна интересная заметка

При рассмотрении приведенной выше задачи вы можете задаться вопросом, является ли обозначение Big O обозначением O(2(n)), поскольку мы дважды выполняем цикл? Если цикл имеет значение O(n), то мы выполнили его дважды: один раз для создания объекта JavaScript, а второй раз для повторной обработки списка и проверки, есть ли у нас два числа, сумма которых равна заданному числу.

Если вы помните, я говорил, что нас волнуют в основном только циклы, добавьте здесь звездочку, чтобы сказать, что нас волнует наибольшая величина операции, присутствующая в задаче. Что это значит?

  • Если в вашей программе есть цикл с производительностью O(n), а позже в коде есть вложенный цикл с производительностью O(n^2), мы называем большой O просто O(n^2) — экспонента — это поведение самого высокого порядка величины в программе, она же наибольшее беспокойство. Поэтому мы отбрасываем меньшую.
  • Если у вас есть вложенный цикл, выполняющийся за O(n^2), а затем тройной вложенный цикл, выполняющийся за O(n^3), мы упростим это до кубического времени. Тройной вложенный цикл — это самый высокий порядок величины, происходящий в коде, поэтому мы упрощаем и называем его O(n^3).

Если подумать, то так будет справедливее. Почти все, что вы напишете, будет иметь некоторые операции, которые являются O(1), но почти никогда нельзя точно сказать, что общая производительность программы равна O(1). Если в ней есть один цикл, это утверждение не будет точным.

Заключение

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

Кроме того, вот еще несколько замечательных ресурсов:

  • Нотация Big O с примерами
  • Алгоритмы на простом английском языке, временная сложность и нотация Big O

Оцените статью
devanswers.ru
Добавить комментарий