Понимание того, как нотация Big O используется для измерения производительности алгоритмов.
Big O — это фундаментальная концепция в области компьютерных наук, но большинство людей не понимают, что это такое и зачем она нужна. Кроме того, она очень сложна для понимания новичками. В этой статье мы разберем понятие Big O, поймем его важность и рассмотрим, как его можно использовать для определения эффективности алгоритмов.
Необходимые условия
-
Базовое понимание структур данных, таких как массивы.
-
Базовые знания JavaScript (наши примеры приведены на синтаксисе javascript).
Что такое Big O?
Это изображение выше объясняет Big O как «нахождение асимптотической верхней границы», но мы здесь не за этим, мы пришли за более упрощенным объяснением, а не за этим 😂😂😂😂. Итак, давайте дадим определение.
Big O — это способ выражения и представления производительности алгоритма. Алгоритм — это пошаговый подход к решению проблем, и важно знать, что проблема может иметь несколько алгоритмов для поиска ее решения, а нотация Big O — это стандарт для определения наиболее оптимального/эффективного алгоритма.
Big O измеряет производительность алгоритма с точки зрения двух факторов, а именно: количества времени, которое требуется для его завершения, и объема памяти, который он потребляет. Таким образом, существует два способа измерения производительности любого алгоритма с помощью Big O;
- Временная сложность.
- Пространственная сложность.
Временная сложность
Временная сложность — это то, как быстро алгоритм достигает своей цели. По сути, это то, сколько времени потребуется алгоритму для достижения своей цели, и это определяется тем, насколько хорошо он работает при увеличении количества операций.
Пространственная сложность
Это то, сколько памяти потребляет алгоритм при выполнении поставленной задачи. Пространственная сложность алгоритма определяется объемом памяти, необходимым для решения одного экземпляра вычислительной задачи.
Важность Big O
Важное значение Big O заключается в том, что он служит стандартом для сравнения алгоритмов. Как мы уже говорили, для решения одной задачи может использоваться несколько алгоритмов, и Big O — это способ определить наиболее эффективный алгоритм для решения этой задачи.
Другие цели Big O включают следующее;
-
Определение наихудшего времени работы алгоритма в зависимости от размера его входных данных.
-
Анализ алгоритмов с точки зрения масштабируемости и эффективности.
Типы нотаций Big O
Существует несколько нотаций Big O, но прежде чем мы погрузимся в них, давайте проанализируем изображение ниже.
Это изображение — формат, используемый для представления нотаций Big O, и его можно разбить на следующие две части.
- O, что означает Big O
- n, обозначающее количество операций.
Примечание: Количество операций представляет собой количество задач/действий, которые обрабатывает алгоритм.
С помощью приведенной ниже диаграммы мы обсудим типы обозначений Big O, сосредоточившись на трех (3) лучших обозначениях.
Изображение выше — это диаграмма, показывающая несколько нотаций Big O, а цвета обозначают следующее;
-
Красная область 🟥 представляет собой наихудший сценарий для любого алгоритма. В этой области мы имеем обозначения O(N!), O(N²), O(2ⁿ) и O(N log N).
-
Желтая область 🟨 представляет собой промежуточный сценарий любого алгоритма. Любой алгоритм в этой области является подходящим и нормальным, по сравнению с алгоритмами в красной области. Она состоит из обозначения O(N).
-
Зеленая область 🟩 представляет собой наилучший сценарий любого алгоритма. Это желаемое состояние каждого алгоритма, и оно состоит из обозначений O(1) и O(log N).
Теперь давайте углубимся в желтую и зеленую области, которые состоят из следующих обозначений;
- O(1) — постоянная сложность
- O(N) — линейная сложность
- O(Log N) — логарифмическая сложность
O(1)- постоянная сложность
Алгоритмы постоянного времени используют нотацию O(1), что означает, что их временная сложность постоянна. Независимо от количества входных данных, которые они получают, алгоритмы постоянного времени выполняются за одинаковое время.
Таким образом, если вам дано;
-
1 вход, то алгоритм выполнится за 1 секунду
-
10 входов — за 1 секунду
-
100 000 входов, то он выполнится за 1 секунду.
Рассмотрим пример кода.
const example1 = function (names) {
console.log(names[0]);
};
example1(["Aahil", "grace", "joseph", "matilda", "patience", "Austin"]);
В примере выше мы создали функцию example1, которая принимает на вход массив имен. Функция просто создана для выполнения одного (1) действия — вывода в консоль браузера первого имени из массива.
Вывод 👇
Приведенный выше пример имеет постоянную временную сложность, и можно сказать, что он выполняет постоянное количество операций независимо от входных данных. То есть, даже если мы найдем третье и последнее имя из массива, время выполнения этой задачи будет постоянным, потому что она выполняет одну и ту же операцию — нахождение имени из массива.
Примечание: O(1) — это наилучший случай для любого алгоритма.
O(N) — линейная сложность
Алгоритм с обозначением O(N) масштабируется по мере увеличения количества входов и количества операций. По мере увеличения входных данных алгоритмы требуют пропорционально больше времени для выполнения.
Таким образом, если дано;
-
1 вход, то будет выполнена 1 операция.
-
10 входов, то будет выполнено 10 операций.
-
100 000 входов — будет выполнено 100 000 операций.
Он имеет линейную производительность либо во временной, либо в пространственной сложности. С увеличением количества входов увеличивается количество операций, и время, необходимое для их выполнения, также увеличивается.
Например, при чтении книги требуется больше времени, чтобы ее закончить, в зависимости от того, сколько в ней страниц. Поэтому на чтение книги из 10 страниц уйдет меньше времени, чем на чтение книги из 1000 страниц. Это более понятный пример, теперь давайте рассмотрим практический пример кода.
const example2 = function (names) {
for (const name of names) console.log(name);
};
example2(["Aahil", "grace", "joseph", "matilda", "patience", "Austin"]);
В нашем примере выше мы создали функцию example2, которая принимает массив имен в качестве входных данных. Функция содержит цикл for...of, который просматривает массив имен и выводит каждое имя в массиве на консоль. Функция вызывается с массивом из 6 имен.
Вывод 👇
В этом примере, если бы в массив было добавлено больше имен, потребовалось бы больше времени, поэтому можно сказать, что он имеет линейную временную сложность.
Что касается пространственной сложности, мы создали всего одну переменную, но эта переменная будет занимать место, эквивалентное хранению всех имен в массиве. Поэтому, по мере увеличения имен в массиве, увеличивается и размер переменной.
O(Log N) — логарифмическая сложность
В алгоритме, сложность которого равна O(log N), количество операций увеличивается очень медленно с ростом размера входных данных. При экспоненциальном росте размера входных данных время вычислений почти не увеличивается.
Поэтому, если вам даны;
-
1 вход, он будет работать за 1 секунду
-
10 входов — за 2 секунды.
-
100 входов — за 3 секунды.
Примечание: Ниже перечислены некоторые моменты, которые следует отметить в отношении O(log N);
- Примером O(log N) является двоичный поиск.
- Он гораздо более производителен, чем алгоритм с O(N).
Ниже приведена сводная таблица, которая объясняет природу большинства обозначений Big O.
Из приведенной таблицы видно, что нотации в красной области, такие как O(N!), являются неоптимизированными и дают очень большие сложности с точки зрения пространства и времени независимо от количества входов. Алгоритмы с обозначениями в красной области требуют больше времени для завершения при больших входных данных и занимают много места/памяти. Поэтому рекомендуется оптимизировать или игнорировать алгоритмы с такими обозначениями при решении задач.
Следует также отметить, что O(1) — это наилучшая производительность, которую может иметь алгоритм. Большинство алгоритмов могут быть оптимизированы, чтобы попасть в желтую или зеленую область предыдущего графика, т.е. O(1), O(log N) и O(N), в зависимости от определенных компромиссов.
Заключение
Поскольку мы подошли к завершению этой статьи и, надеюсь, смогли выполнить все цели, поставленные в начале, я хотел бы заключить, что нотация Big-O показывает, насколько хорошо алгоритмы справляются с большими задачами, такими как сортировка или поиск в больших списках.