Big O Notation Time and Space Complexity

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

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

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

Мы измеряем скорость алгоритма, основываясь на приблизительном количестве шагов, которое требуется для его выполнения. Я говорю “приблизительное”, потому что Big O на самом деле призван быть простым и давать высокоуровневое объяснение. При использовании Big O мы игнорируем построчные детали кода и не заботимся о каждом отдельном вычислении.

Мы вычисляем Big O относительно размера входных данных, который мы обозначаем n . Поэтому если нам дан массив, то array.length == n . Мы используем букву n, потому что хотим знать, сколько операций потребуется алгоритму при любой длине массива.

Если мы пройдемся по массиву один раз с помощью цикла for, мы коснемся каждого элемента – или всех n элементов. С помощью этого единственного цикла мы говорим, что для входного массива длиной n наша функция требует O( n ) операций. Другие вычисления, происходящие внутри цикла for, нас не волнуют.

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

Как оцениваются кандидаты при приеме на работу

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

Определение того, будет ли кто-то принят на работу, основывается на трех общих показателях:

1. Опыт (опыт работы или личные проекты)
2. Мягкие навыки (будете ли вы хорошим партнером в команде и будете ли вы с энтузиазмом относиться к продукту)
3. Код (можете ли вы эффективно решать проблемы).

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

Код будет оцениваться по двум факторам:

1. масштабируемость (объективный)
2. читабельность (субъективный)

Когда мы говорим о масштабируемости, мы имеем в виду сложность Big O алгоритма и количество операций, которые потребуются для его выполнения.

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

Например, если у нас есть два алгоритма, которые решают задачу на O( n ) и O( n 2 ), мы можем объективно сказать, что O( n ) лучше, потому что мы знаем, что он потребует меньше операций. Решение O( n ) будет касаться каждого элемента на входе в общей сложности n раз, а решение O( n 2 ) будет касаться элементов на входе n x n раз.

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

Советы, если Big O для вас в новинку

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

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

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

Что означает Big O

Big O определяет, как алгоритм масштабируется.

Другой способ сказать это – Big O определяет, насколько быстро наш алгоритм обрабатывает очень большое количество элементов.

1. Мы оцениваем скорость на основе количества шагов, а не расчетного времени (т.е. секунд или минут).
2. Нас интересуют только те шаги, которые увеличиваются в зависимости от размера входных данных.

n – это не точное число. Оно просто означает, когда входные данные становятся “очень большими”. Для себя я просто представляю n = 1000000, чтобы выразить это в реальных терминах. Это достаточно большой размер, чтобы быть значимым, но не настолько большой, чтобы потеряться во всех 0.

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

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

Как же Big O на самом деле определяет это?

Давайте проведем мысленный эксперимент. Допустим, у нас есть следующие функции:

Если им дать одинаковые входные данные, как мы узнаем, какая из них требует больше времени для выполнения?

• Что если размер входных данных n составляет всего 1 элемент?
• Что если размер входного сигнала n составляет 1 000 000 элементов?
• Что если #2 будет выполняться на вашем мобильном телефоне, а #3 – на суперкомпьютере?
• Что, если мы выполним #2 локально, а #3, вызвав API на удаленном сервере?

Если мы попытаемся определить по времени, какой алгоритм быстрее, то это полностью зависит от среды и объема данных. Для n = 1 элемента на входе все они завершатся почти мгновенно.

Однако если мы запустим функции на одном и том же компьютере для 1 000 000 элементов, #1 все равно завершится мгновенно, а вот #2 завершится гораздо быстрее, чем#3.

#1 не имеет зависимости от входных данных. Независимо от размера данных, он всегда будет выполнять одно и то же количество операций, поэтому мы называем это постоянное время O(1) . Он выполняет одно и то же количество операций каждый раз, потому что цикл всегда переходит от 0 к 20, независимо от значения, используемого для ввода.

Поскольку в #2 используется один цикл for, он будет итерировать вход для всех 1,000,000 элементов один раз, и это то, что мы называем O( n ) .

В #3 есть вложенные циклы for, поэтому он будет итерировать вход 1,000,000 раз для всех 1,000,000 элементов, в общей сложности 1,000,000,000,000, и это делает его алгоритмом O( n 2 ). То есть 1 миллион против 1 триллиона операций для #2 и #3.

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

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

Хотя об этом не будут спрашивать на собеседованиях, давайте посмотрим, как различная сложность Big O примерно отразится на времени, необходимом для завершения алгоритма, когда мы нормализуем операцию O( n ) с 1 миллиардом элементов до 1 секунды. В нашем мысленном эксперименте разница во времени O( n ) и O( n 2 ) при 1 миллионе элементов составит 1 мс против 16,7 минуты. Это разница между молниеносной скоростью и “поломкой” с точки зрения пользователя.

Размер входных данных	log n	n	n log n	n 2	2 n	n!
10	0.003ns	0.01ns	0.033ns	0.1ns	1ns	3.65мс
20	0.004ns	0.02ns	0.086ns	0.4ns	1мс	77 лет
30	0.005ns	0.03ns	0.147ns	0.9ns	1 сек	8.4×10 15 лет
40	0.005ns	0.04нс	0.213нс	1.6ns	18.3мин	—
50	0.006ns	0.05ns	0.282ns	2.5ns	13 дней	—
100	0.07	0.1ns	0.644нс	0.10ns	4×10 13 лет	—
1,000	0.010ns	1.00ns	9.966нс	1мс	—	—
10,000	0.013ns	10нс	130нс	100 мс	—	—
100,000	0.017ns	0.10мс	1.67мс	10 секунд	—	—
1’000,000	0.020ns	1мс	19.93мс	16.7мин	—	—
10’000,000	0.023ns	0.01сек	0.23мс	1.16 дней	—	—
100’000,000	0.027ns	0.10сек	2.66сек	115.7 дней	—	—
1,000’000,000	0.030ns	1 сек	29.90сек	31,7 года	—	—

4 шага для вычисления Big O

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

Есть 4 шага, которые мы выполним:

1. Худший случай
2. Отбросить константы
3. Отбросить менее значимые члены
4. Учет всех входных данных

Шаг 1. Наихудший случай

Когда мы рассчитываем временную сложность Big O алгоритма, мы основываемся на наихудшей возможности.

Мы хотим, чтобы наша Big O описывала самую узкую верхнюю границу нашей функции.

Рассмотрим этот простой пример:

В лучшем случае мы итерируем только 1 элемент, поэтому мы действительно находим элемент за время O(1) – размер входа не имеет значения, и это краевой случай. Это очень редкий сценарий, и он не имеет большого значения.

В среднем случае мы итерируем половину массива элементов, что составляет O( 0.5 n ) . (Но мы также отбрасываем константы, что вы увидите в шаге 2).

В худшем случае нам придется просмотреть весь массив, чтобы найти последний элемент, что составляет O( n ) .

Представьте, что это было в производстве, и мы хотели бы искать в массиве из 1 000 000 000 элементов. 25% времени мы будем ожидать, что нам придется перебирать по меньшей мере 750 000 000 000 элементов. Это все равно очень много людей, у которых будет плохой опыт.

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

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

Шаг 2. Отбросьте константы

Вы, наверное, заметили, что когда мы говорим о Big O, мы упоминаем только n и не говорим о таких вещах, как 5n или O(2n + 3n). Мы позволяем себе игнорировать константы, потому что это потребовало бы слишком много знаний о том, что происходит в компиляторе или как система оптимизирует наш код и преобразует его в машинный язык.

Как мы уже говорили, Big O должно быть простым. Попытка учесть все операции добавляет тонну сложностей, не предоставляя никакой новой информации. Посмотрите на пример ниже, чтобы понять, почему.

Так что же такое это “Большое О”? У вас может возникнуть соблазн сказать, что функция case1 имеет размер O( 3n ), потому что у нас есть 3 отдельных цикла. Однако в case2 мы все еще вызываем нашу функцию print столько же раз. Мы также не знаем, как наш язык программирования будет интерпретировать этот код и как он будет выполняться под капотом.

Теперь давайте подумаем, что произойдет, если мы передадим 1 000 000 элементов всем трем функциям. Мы полагаем, что case1 и case2 могут выполнить от 1 до 3 миллионов операций. Однако case3 выполняет 1,000,000 2 или 1,000,000,000,000 операций. Разница между 1 и 3 миллионами становится несущественной по сравнению с 1 триллионом операций.

Мы позволяем себе принять тот факт, что нас волнует только тенденция развития алгоритма по мере его масштабирования с большим размером входных данных, и сравниваем только времена выполнения разного порядка сложности, т.е. O( n ) против O( n 2 ).

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

Шаг 3. Отбросьте менее значимые термины

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

Мы можем сделать еще один шаг дальше и сказать, что если в алгоритме есть операции, которые используют различные сложности времени Big O, мы рассматриваем только самую медленную Big O. Например, если в функции есть O( n 2 ) и O( n ), мы просто скажем, что функция работает за время O( n 2 ).

При размере входных данных 1,000,000, у нас будет 1000000 + 10000000000 = 1000001000000 операций. Используя нашу таблицу выше, это будет 16,7 минут + 1 миллисекунда, что делает миллисекунду бессмысленной. Больший срок является настолько непреодолимым, что мы позволяем себе сократить решение до простого O( n 2 ) .

Шаг 4. Учет всех входных данных

Бывают задачи, в которых мы получаем несколько структур входных данных. Если мы не можем сделать никаких предположений об их размере, то при расчете сложности Big O нам нужно учесть их обе. Наиболее распространенный синтаксис – обозначить один вход как n элементов, а другой – как m элементов.

Обычный Big O

Визуализация Big O

Вот некоторые из наиболее распространенных временных сложностей от самой быстрой до самой медленной.

O(1) – постоянное время

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

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

O(log n ) – логарифмическое время

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

Повторное деление сокращает наше решение так быстро, что O(log n ) является молниеносным, даже для очень больших n.

O( n ) – линейное время

Это происходит, когда мы итерируем нашу структуру входных данных один раз (или последовательно). До тех пор, пока мы не вложим циклы, мы будем работать в линейном времени.

Если у нас есть входной массив длиной 1,000,000, наш цикл for будет перебирать миллион элементов. Если у нас есть входной массив длиной 1 000 000 000 000, наш цикл for будет итерировать один миллиард элементов. Время O( n ) означает, что количество необходимых операций просто равно длине входного массива. Операции и размер входа увеличиваются 1 к 1, или линейно.

Это относится и к другим методам итерации, таким как forEach, map, filter, reduce. Все они выполняют итерацию через нашу структуру входных данных один раз, как и цикл for.

O( n log n ) – логарифмически линейный

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

Причина O( n ) < O( n log n ) < O( n 2 ) is that log(n) is greater than 1 and less than n . So for O( n log n ) , we multiply n times a number that is 1 < log(n) < n .

O( n 2 ) – квадратичное время.

Это происходит, когда мы вставляем циклы. Решения методом перебора часто требуют квадратичного времени и редко являются приемлемыми в качестве окончательного ответа.

Чем больше вложенность, тем больше увеличивается экспонента. Если у вас три вложенных цикла, то сложность становится O( n 3 ) .

Общее название для случаев, когда мы возводим n в степень, известно как полиномиальное время. Квадратичное время означает, что у нас есть полиномиальное время, когда мы знаем, что экспонента равна 2.

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

O( 2 n ) и O( n!).

Случаи, которые хуже, чем O( n 2 ), немного более редкие и специфические. Мы будем рассматривать их по мере необходимости в курсе, но оба сценария очень плохи и их следует избегать любой ценой.

Примером O( 2 n ) является рекурсивный алгоритм грубой силы для вычисления числа Фибоначчи. Этот вопрос рассматривается далее в модуле рекурсии и в модуле динамического программирования.

Наихудшая сложность – O( n! ), и это происходит, когда вы вычисляете все перестановки входных данных.

Сложность пространства

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

С увеличением важности быстрого программного обеспечения и снижением цены на память, временная сложность стала доминирующим фактором. Однако мы не можем игнорировать пространство. Нехватка памяти – это реальная проблема в программной инженерии, которая может привести к аварийному завершению нашей программы. Память (пространство, доступное для выполнения нашей программы) – это ограниченный ресурс, который мы должны учитывать.

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

Амортизированное время

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

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

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

Примером может служить динамический массив, который изменяет размер и удваивает свою емкость каждый раз, когда он заполняется. Толчок к массиву занимает O(1) времени. Если в массиве 1 000 000 элементов и емкость 2 000 000, то мы можем подтолкнуть массив 999 999 раз за время O(1), прежде чем его размер изменится один раз за время O( n ).

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

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