Что такое o большое

Big O

Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».

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

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных

Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

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

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.

Начнем с самого простого: O(1)

Возьмем массив из 5 чисел:

Допустим надо получить первый элемент. Используем для это индекс:

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

Другими словами: насколько возрастет кол-во операций при увеличении кол-ва входных параметров.

В нашем примере входных параметров 5, потому что в массиве 5 элементов. Для получения результата нужно выполнить одну операцию (взять элемент по индексу). Сколько операций потребуется если элементов массива будет 100? Или 1000? Или 100 000? Все равно нужна только одна операция.

Т.е.: «одна операция для всех возможных входных данных» — O(1).

O(1) можно прочитать как «сложность порядка 1» (order 1), или «алгоритм выполняется за постоянное/константное время» (constant time).

Вы уже догадались что O(1) алгоритмы самые эффективные.

Итерации и «время порядка n»: O(n)

Теперь давайте найдем сумму элементов массива:

Опять зададимся вопросом: сколько операций на ввод нам потребуется? Здесь нужно перебрать все элементы, т.е. операция на каждый элемент. Чем больше массив, тем больше операций.

Используя Big O нотацию: O(n), или «сложность порядка n (order n)». Так же такой тип алгоритмов называют «линейными» или что алгоритм «линейно масштабируется».

Анализ

Можем ли мы сделать суммирование более эффективным? В общем случае нет. А если мы знаем, что массив гарантированно начинается с 1, отсортирован и не имеет пропусков? Тогда можно применить формулу S = n(n+1)/2 (где n последний элемент массива):

Такой алгоритм гораздо эффективнее O(n), более того он выполняется за «постоянное/константное время», т.е. это O(1).

Фактически операций не одна: нужно получить длину массива, получить последний элемент, выполнить умножение и деление. Разве это не O(3) или что-нибудь такое? В Big O нотации фактическое кол-во шагов не важно, важно что алгоритм выполняется за константное время.

Алгоритмы с константным временем это всегда O(1). Тоже и с линейными алгоритмами, фактически операций может быть O(n+5), в Big O нотации это O(n).

Не самые лучшие решения: O(n^2)

Давайте напишем функцию которая проверяет массив на наличие дублей. Решение с вложенным циклом:

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

Алгоритмы с вложенными циклами по той же коллекции всегда O(n^2).

«Сложность порядка log n»: O(log n)

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

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

Пускай массив будет отсортирован. Тогда мы сможем использовать алгоритм «бинарный поиск»: делим массив на две половины, отбрасываем не нужную, оставшуюся опять делим на две части и так пока не найдем нужное значение. Такой тип алгоритмов называется «разделяй и влавствуй» Divide and Conquer.

Этот алгоритм основан на логарифме.

Быстрый обзор логарифмов

Рассмотрим пример, чему будет равен x?

Нужно взять кубический корень от 8 — это будет 2. Теперь посложнее

С использованием логарифма задачу можно записать так

«логарифм по основанию 2 от 512 равен x». Обратите внимание «основание 2», т.е. мы мыслим двойками — сколько раз нужно перемножить 2 что бы получить 512.

В алгоритме «бинарный поиск» на каждом шаге мы делим массив на две части.

Мое дополнение. Т.е. в худшем случае делаем столько операций, сколько раз можем разделить массив на две части. Например, сколько раз мы можем разделить на две части массив из 4 элементов? 2 раза. А массив из 8 элементов? 3 раза. Т.е. кол-во делений/операций = log2(n) (где n кол-во элементов массива).

Получается, что зависимость кол-ва операций от кол-ва элементов ввода описывается как log2(n)

Таким образом, используя нотацию Big O, алгоритм «бинарный поиск» имеет сложность O(log n).

Улучшим O(n^2) до O(n log n)

Вернемся к задачке проверки массива на дубли. Мы перебирали все элементы массива и для каждого элемента еще раз делали перебор. Делали O(n) внутри O(n), т.е. O(n*n) или O(n^2).

Мы можем заменить вложенный цикл на бинарный поиск*. Т.е. у нас остается перебор всех элементов O(n), внутри делаем O(log n). Получается O(n * log n), или O(n log n).

* ВНИМАНИЕ, во избежание Импринтинга. Использовать бинарный поиск для проверки массива на дубли — плохое решение. Здесь лишь показывается как в терминах Big O оценить сложность алгоритма показанного в листинге кода выше. Хороший алгоритм или плохой — для данной заметки не важно, важна наглядность.

Что такое «O» большое в программировании?

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

Дело в том, что время выполнения написанной программы зависит от переданных входных данных.

Но как выяснить, эффективна ли программа? Есть ли способ это определить? Как проверить, при передаче каких входных данных программа работает лучше всего?

Прежде чем перейти к ответам, разберемся с тем, как вообще работает эффективная программа. И в этом поможет одна забавная история.

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

Один метод заключался в использовании почтового голубя, к лапке которого привязали USB-флешку.

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

Самое интересное заключалось в том, что голубь обогнал интернет. Но как?

Если голубю потребовалось время, чтобы добраться до места, независимо от размера данных, то время достижения интернет-сигнала меняется в зависимости от размера данных.

Перейдем к вычислительным сложностям

Вот две сложности, связанные с программированием.

• Временная: время, необходимое для обработки входных данных.
• Пространственная: количество места, требуемое для обработки входных данных.

Что такое нотация “О” большое?

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

Проще говоря, термином “О” большое определяется, как время выполнения растет по мере увеличения входных данных.

• Увеличение времени выполнения. Поскольку время, необходимое для выполнения программы, зависит от процессора компьютера, используется “О” большое, чтобы показать, как меняется время выполнения.
• Ввод данных. Поскольку проверяется не только время, которое требуется для выполнения программы, но и ввод, в нотации “О” большое есть “n”, которое определяет количество элементов обрабатываемых входных данных. Поскольку время выполнения растет с увеличением размера входных данных, эту величину можно представить в виде O(n).
• По мере увеличения входных данных. По мере увеличения входных данных программам иногда требуется больше времени для выполнения, что приводит к проблемам с производительностью. Поэтому разрабатываемую программу нужно проверять по мере увеличения входных данных.

Визуализированные примеры

O(1) не увеличивается с изменением размера входных данных. Таким образом, время обработки O(1) — величина постоянная независимо от того, какие входные данные были переданы.

Пример:

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

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

Пример:

Показывает производительность пропорционально размеру входных данных. O(n²) представляет наихудшую производительность.

Пример:

Логарифмическая | O(log n)

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

Пример:

Для данной программы с любыми итерациями значение i = i*2. Поэтому на n-й итерации значение i= i*n и i всегда меньше размера самого цикла (N).

Следовательно, можно получить:

Таким образом, наихудшая временная сложность такого алгоритма будет равна O(log(n)).

Отбросим константы

Существует вероятность того, что O(N) код быстрее, чем O(1) код для определенных входных данных. “О” большое просто описывает скорость увеличения. По этой причине мы отбрасываем константу, что означает, что O(3N) на самом деле O(N):

• O(3N) → O(N)

Можно отбросить не только константы, но и неглавные члены:

• O(N3+N) → O(N3)
• O(N+logN) → O(N)
• O(2∗2N + 1000N100) → O(2N)

Как вычислить сложность?

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

О большое: что это такое, почему это важно, и почему это не важно.

Очень интересная статья Shen Huang о нотации О большое: Big O notation: why it matters, and why it doesn’t
В статье присутствует математические формулы, формальные определения, математические доказательства и т.п. При переводе возможно были допущены не точности в этих понятиях. Но тем не менее статья очень интересна для получения базовых знаний, о том что такое нотации Большое О, зачем оно нужно и какие бывают варианты нотаций.

Вы действительно понимаете что такое О большое (Big O)? Если это так, то эта статья поможет вам освежить ваши знания перед собеседованием. Если нет, эта статья расскажет вам о том что это такое и зачем нужно об этом знать.

Нотация О большое является одним из самых фундаментальных инструментов анализа сложности алгоритма. Эта статья написана с предположением, что вы уже являетесь программистом и за вашими плечами большое количество написанного кода. Кроме того, для лучшего понимания материала потребуется знания основ математики средней школы. И так если вы готовы, давайте начнем!

Picture of a Mandelbrot set, which relates to Complex Numbers and Recursions, Pixabay

Содержание

1. Что такое нотация О большое и почему это важно
2. Формальное определение обозначения О большое
3. О большое (Big O), О малое (Little O), Омега (Omega) и Тета (Theta)
4. Сравнение сложности между всеми нотациями
5. Время и пространство сложности
6. Лучшая, Средняя, Худшая, Ожидаемая Сложность
7. Почему О большое может быть не важна
8. Заключение…

1. Что такое нотация О большое и почему оно важно

«Нотация О большое — это математическая нотация, которая описывает ограничивающее поведение функции, когда аргумент стремится к определенному значению или бесконечности. Он является членом семейства нотаций, изобретенных Полом Бахманом, Эдмундом Ландау и другими, которые в совокупности называются нотациями Бахмана-Ландау или асимптотическими нотациями ».

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

Чтобы понять, что такое О большое, мы можем взглянуть на типичный пример O (n²), который обычно произносится как «Большой O в квадрате». Буква «n» здесь представляет размер входных данных, а функция «g (n) = n²» внутри «O ()» дает нам представление о том, насколько сложен алгоритм по отношению к количеству входных данных.

Типичным алгоритмом со сложностью O(n²) будет алгоритм сортировки выбором. Сортировка выбором — это алгоритм сортировки, который выполняет итерацию по списку, чтобы гарантировать, что каждый элемент с индексом i является i-м наименьшим/наибольшим элементом списка. Наглядный пример.

Алгоритм может быть описан следующим кодом. Чтобы убедиться, что i-й элемент является i-м наименьшим элементом в списке, этот алгоритм сначала просматривает список с помощью цикла for. Затем для каждого элемента он использует другой цикл for, чтобы найти наименьший элемент в оставшейся части списка.

В этом сценарии мы рассматриваем переменную List как входные данные, поэтому размер ввода n — это количество элементов внутри List. Предположим, что оператор if, а присвоение значения, ограниченное оператором if, занимает постоянное время. Затем мы можем найти О большое для функции SelectionSort, проанализировав, сколько раз выполняются операторы.

Сначала внутренний цикл for выполняет операторы внутри n раз. А затем, после увеличения i, внутренний цикл for выполняется n-1 раз … пока он не будет запущен еще один раз, тогда оба цикла for достигнут своих условий завершения.

Selection Sort Loops Illustrated

На самом деле это в конечном итоге дает нам геометрическую сумму, и благодаря математики средней школе мы обнаружим, что внутренний цикл будет повторяться 1 + 2… + n раз, что равно n(n-1)/2 раза. Если мы умножим это, мы получим n²/2-n/2.

Когда мы вычисляем О большое, мы заботимся только о доминирующих операторах, и не заботимся о коэффициентах. Таким образом, мы выбираем n² как О большое. Мы записываем его как O(n²), а произносим как «О большое в квадрате».

Теперь вам может быть интересно, что это за «доминирующие операторы»? И почему нас не волнуют коэффициенты? Не волнуйтесь, мы рассмотрим эти вопросы по очереди далее.

2. Формальное определение нотации О большое

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

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

Wheat and Chess Board, Image from Wikipedia

Так сколько зерна пшеницы должен царь мудрецу? Мы знаем, что шахматная доска имеет 8 квадратов на 8 квадратов, что в сумме составляет 64 фишки, поэтому в итоговой фишке должно быть 2⁶⁴ зерна пшеницы. Если вы проведете самостоятельный расчет, вы получите 1,8446744 * 10¹⁹, то есть около 18, за которыми следуют 18 нулей. Предполагая, что каждое зерно пшеницы весит 0,01 грамма, это дает нам 184 467 440 737 тонн пшеницы. А 184 миллиарда тонн — это много, не правда ли?

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

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

Ниже приведено формальное определение Большого O:

CSE 373 Slides from University of Washington

Формальное определение полезно, когда вам нужно выполнить математическое доказательство. Например, сложность для сортировки выбором может быть определена функцией f (n) = n²/2-n/2, как мы обсуждали в предыдущем разделе.

Если мы допустим, чтобы наша функция g(n) была n², мы можем найти константу c = 1 и N₀ = 0, при условии, N > N₀, где N² всегда будет больше, чем N²/2-N/2. Мы можем легко доказать это, вычитая N²/2 из обеих функций, тогда мы можем видеть, что N²/2 > -N/2 будет истинно, когда N>0. Поэтому мы можем прийти к выводу, что f(n) = O (n²), в другом порядке выбора это «О большое квадрат».

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

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

Но прежде чем мы пойдем дальше, давайте проверим ваше понимание следующим вопросом. Ответ будет приведен в следующем разделе.

Вопрос: Допустим изображение представлено двумерным массивом пикселей. Вы используете вложенный цикл for для итерации по каждому пикселю (то есть у вас есть цикл for, проходящий по всем столбцам, и другой цикл внутри, чтобы пройти по всем строкам). Какая в этом случае будет сложность алгоритма?

3. О большое, O малое, Омега и Тета

Ниже приведены формальные математические определения этих нотаций:

О большое: «f(n) есть O(g (n))» тогда и только тогда, когда некоторые константы c и N₀, f(N) ≤ cg(N) для всех N> N₀

Малое O: «f(n) есть o (g(n))», если f(n) есть O(g(n)) и f(n) не есть Θ(g(n))

Омега: «f(n) есть Ω(g(n))» тогда и только тогда, когда некоторые константы c и N₀, f(N) ≥ cg(N) для всех N> N₀

Тета: «f (n) есть Θ(g (n))» тогда и только тогда, когда f(n) есть O(g(n)), а f(n) есть Ω(g(n))

• О большое (O()) описывает верхнюю границу сложности.
• Малое O (o()) описывает верхнюю границу, исключая точную оценку.
• Омега (Ω ()) описывает нижнюю границу сложности.
• Тета (Θ ()) описывает точную оценку сложности.

Например, функция g(n) = n² + 3n — это O(n³), o(n⁴), Θ(n²) и Ω (n). Но вы все равно были бы правы, если бы сказали, что это Ω(n²) или O(n²).

Вообще, когда мы говорим о Большом O, мы на самом деле имеем в виду Тета (Θ Theta). Бессмысленно, когда вы определяете верхнюю границу, намного превышающую объем анализа. Это было бы похоже на решение неравенств путем помещения ∞ на большую сторону, что почти всегда формально сделает вас правым.

Но как определить, какие функции сложнее других?

4. Сравнение сложности между типичными нотациями Больших O

Когда мы пытаемся выяснить О большое для конкретной функции g(n), мы заботимся только о доминирующем операторе (dominant term) функции. Доминирующий оператор — это такой оператор, который растет быстрее всего.

Например, n² растет быстрее, чем n, поэтому, если у нас есть что-то вроде g(n) = n² + 5n + 6, то О большое будет (n²). Если вы когда нибудь проводили некоторые исчисления, это очень похоже на сокращение пределов для дробных многочленов, когда вам важен только доминирующий оператор для числителей и знаменателей в конце.

Another way to look at Big O, Image from Stack Overflow

Но какая функция растет быстрее, чем другие? На самом деле существует довольно много правил.

Complexity Growth Illustration from Big O Cheatsheet

1. O(1) имеет наименьшую сложность

Часто называемый «постоянный по времени», если вы можете создать алгоритм для решения проблемы с O(1), то это будет лучший выбор алгоритма. В некоторых сценариях сложность может выходить за пределы O(1), тогда мы можем проанализировать их, найдя ее аналог O(1/g(n)). Например, O(1/n) является более сложным, чем O(1/n²).

2. O (log(n)) является более сложным, чем O(1), но менее сложным, чем полиномы

Поскольку сложность часто связана с алгоритмами «разделяй и властвуй», O (log(n)) — это, как правило, хорошая сложность, которую можно достичь для алгоритмов сортировки. O (log(n)) является менее сложным, чем O (√n), потому что функцию квадратного корня можно считать полиномом, где показатель степени равен 0,5.

3. Сложность многочленов увеличивается с ростом степени

Например, O (n⁵) является более сложным, чем O (n⁴).

4. Экспоненты имеют большую сложность, чем полиномы, если коэффициенты положительные кратные n

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

5. Факториалы имеют большую сложность, чем степень

Если вам интересны доказательства, посмотрите Гамма-функцию (Gamma function), это аналитическое продолжение факториала. Краткое доказательство состоит в том, что и факториалы, и степень имеют одинаковое количество умножений, но числа, которые умножаются, растут для факториалов, оставаясь неизменными для степени.

6. Умножение

При умножении сложность будет больше, чем оригинал, но не больше, чем эквивалентность умножения чего-то более сложного. Например, O (n*log (n)) является более сложным, чем O (n), но менее сложным, чем O (n²), потому что O (n²) = O (n * n), а n более сложный, чем log (n). ).

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

Вопрос: Расставьте следующие функции от самых сложных до менее.

Examples taken from Textbook Problems

Решение для вопроса из Раздела 2:

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

5. Время и пространство сложности

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

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

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

Bucket Sort Visualization

6. Лучшая, Средняя, Худшая, Ожидаемая Сложность

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

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

Insertion Sort Illustrated, Image from Wikipedia

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

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

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

Big O Cheatsheet for Common Algorithms

Решение для вопроса из Раздела 4:

Осматривая функции, мы можем начать с ранжирования следующих полиномов от наиболее сложного до менее по правилу 3. Где корень квадратный из n равен просто n в степени 0,5.

Тогда, применяя правила 2 и 6, мы получим следующее. Логарифм с основанием 3 может быть преобразован в с основанием 2 (log base conversions). Логарифм с основанием 3 по-прежнему растет немного медленнее, чем с основанием 2, и поэтому в рейтинге получает место после него.

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

Прежде всего, 2 в степени 2 в степени n больше 2 в степени n, а +1 еще больше его увеличивает.

Чтобы степень log (n) с основанием 2 была равна n, мы можем преобразовать следующее. Логарифм от 0,001 растет немного больше, чем просто константы, но меньше, чем почти все остальное.

Выражение, у которого n в степени log (log (n)), на самом деле является вариацией квазиполинома (quasi-polynomial), который больше полинома, но меньше экспоненты. Поскольку log (n) растет медленнее, чем n, его сложность немного меньше. Выражение с обратным логарифмом сходится к константе, поскольку 1 / log (n) расходится к бесконечности.

Факториалы могут быть представлены умножением и, следовательно, могут быть преобразованы в сложения вне логарифмической функции. «N select 2» может быть преобразовано в полином с кубическим членом, являющимся наибольшим.

И, наконец, мы можем ранжировать функции от самых сложных до наименее сложных.

Почему О большое может не имеет значения

. — WARNING — .

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

. — WARNING — .

Поскольку ранее мы узнали, что сложность по времени в наихудшем случае для быстрой сортировки будет O (n²), а для сортировки слиянием (merge sort) будет O (n * log (n)), то сортировка слиянием должна быть быстрее, верно? Ну, вы, наверное, догадались, что ответ неверен. Чтобы это продемонстрировать, я выложил этот пример сюда trinket.io. Он сравнивает время для быстрой сортировки (quick sort) и сортировки слиянием (merge sort). Мне удалось протестировать его только на массивах длиной до 10000 значений, но, как вы можете видеть, время сортировки слиянием растет быстрее, чем быстрой сортировки. Несмотря на быструю сортировку, имеющую худшую сложность O (n²), вероятность этого действительно низка. Когда дело доходит до увеличения скорости, быстрая сортировка имеет более высокую скорость чем сортировка слиянием, ограниченная сложностью O (n * log (n)), быстрая сортировка заканчивается в среднем с лучшей производительностью.

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

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

Заключение…

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

Big O нотация: что это такое и почему ее обязательно нужно знать каждому программисту

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

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

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

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

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

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

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

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

Структуры данных vs абстрактные типы данных

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

Однако, если отделить задачу от способа ее выполнения, вы увидите, что данные инструменты выполняют роль «средства для копания» и являются абстрактным типом данных. То, как вы на самом деле копаете, можно назвать структурой данных. Абстрактный тип данных – это теоретическая сущность, а структура данных – это ее реализация.

Рассмотрим еще один пример. Предположим, вы хотите навестить своего друга, живущего на другом конце города. В вашем распоряжении велосипед, автомобиль и ноги. Здесь транспортное средство – это абстрактный тип данных. То, как вы передвигаетесь – это структура данных.

Это различие важно, так как существует несколько способов выполнения задачи. У каждого из них свои плюсы и минусы, которые зависят от конкретной программы. Так, для рытья ям лучше всего подходит лопата. Однако, для перемещения по городу «правильная» структура данных зависит от внешнего контекста. Например, автомобиль является самым быстрым способом, но для него нужны дороги, тогда как наши ноги медленнее, но могут использовать любые маршруты.

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

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

Альтернативным методом может быть аккуратное размещение одежды в комоде или шкафу. Этот метод имеет высокое время записи и низкое время чтения, поскольку потребуется больше времени, чтобы разложить одежду, но вы сможете быстрее получить доступ к любому предмету, который вы искали.

Данные примеры не далеки от стратегий сброса данных в AWS S3 по сравнению с базой данных или хранения данных в высокоструктурированной базе данных SQL по сравнению с гибкой базой данных NoSQL.

Big O нотация

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

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

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

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

Если же мы выводим каждую пару элементов в массиве, то сложность становится O(n²). Массив из 4 элементов требует 16 шагов, массив из 10 элементов – 100 шагов и так далее.

Алгоритм O(n²) не является идеальным. Нам нужен алгоритм, который работает в постоянном режиме. Или O(1), где время выполнения не зависит от объема данных. Например, печать случайного значения из массива всегда будет занимать одно и то же время, независимо от размера массива.

Можно количественно оценить эффективность этих функций с помощью команды %%timeit в Jupyter Notebook. Ниже видно резкое увеличение времени выполнения O(n²) print_pairs . Также видно силу функции O(1) print_idx , время выполнения которой колеблется около 0.153 мс, независимо от размера массива и от того, какой элемент запрашивается, первый или последний.

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

Однако, для решения каких задач может потребоваться алгоритм из красной зоны? Они необходимы для решения задач, где требуется знать все возможные ответы на вопрос. Одним из таких примеров алгоритма O(2ⁿ) является поиск всех подмножеств массива. Каждый элемент множества может быть либо включен, либо исключен из подмножества. Набор из четырех элементов [A,B,C,D] будет иметь 2⁴ или 16 подмножеств:

1. [] , [A] , [B] , [C] , [D]
2. [A,B] , [A,C] , [A,D] , [B,C] , [B,D] , [C,D]
3. [A,B,C] , [A,B,D] , [A,C,D] , [B,C,D]
4. [A,B,C,D]

Худшее время выполнения у алгоритма O(n!), который представляет из себя перестановки – классический пример n-факторной сложности. Чтобы найти все возможные варианты расположения [A, B, C, D] мы начинаем с одной из четырех букв в первой позиции, затем одну из оставшихся трех во второй позиции и так далее. Таким образом, будет 4 × 3 × 2 × 1, или 24 перестановки :

1. [A,B,C,D] , [A,B,D,C] , [A,C,B,D] , [A,C,D,B] , [A,D,B,C] , [A,D,C,B]
2. [B,A,C,D] , [B,A,D,C] , [B,C,A,D] , [B,C,D,A] , [B,D,C,A] , [B,D,A,C]
3. [C,A,B,D] , [C,A,D,B] , [C,B,A,D] , [C,B,D,A] , [C,D,B,A] , [C,D,A,B]
4. [D,A,B,C] , [D,A,C,B] , [D,B,A,C] , [D,B,C,A] , [D,C,A,B] , [D,C,B,A]

Время выполнения этих задач быстро увеличивается. Массив из 10 элементов имеет 1024 подмножества и 3 628 800 перестановок. Массив из 20 элементов имеет 1 048 576 подмножеств и 2 432 902 008 176 640 000 перестановок.

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

Типы данных

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

• Целые числа (Integers) , такие как 1 , -5 и 256 .

В других языках программирования (кроме Python) вы можете определить тип целого числа. Например, знаковое ( +/- ) или беззнаковое (только + ), а также количество бит, которое может содержать целое число.

• Числа с плавающей запятой (Float) – это числа с десятичными знаками. Например, 1.2 , 0.14 .

В Python к ним относятся числа, определенные с помощью научной нотации, такие как 1e5 . В более низкоуровневых языках, например, C или Java, есть родственный тип double . Он обозначает дополнительную точность после запятой.

• Заголовки (Chars) – это буквы a , b , c . Их набор – это строка, которая технически является массивом chars . Строковые представления чисел и символов, таких как 5 или ? , тоже являются символами.

• Void – ноль, как None в Python. Указывает на отсутствие данных. Это помогает при инициализации массива, который будет заполняться. Например, функция, которая выполняет действие, но ничего не возвращает. Такая, как отправка электронного письма.

В следующей части материала мы приступим к изучению массивов и связанных списков.