Изучение нотации Big O со сложностью O(n)

Нотация Big O – одна из тех вещей, которым меня учили в университете, но я так и не смог понять ее суть. Я знал достаточно, чтобы ответить на очень простые вопросы по ней, но не более того. С тех пор ничего не изменилось, поскольку я не использовал и не слышал, чтобы кто-то из моих коллег упоминал ее с тех пор, как начал работать. Поэтому я решил потратить некоторое время на то, чтобы вернуться к этому вопросу, и написал этот пост, в котором кратко изложил основы нотации Big O Notation и привел несколько примеров кода, чтобы помочь объяснить ее.

Итак, что такое нотация Big O? В простых терминах:

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

Теперь кратко рассмотрим синтаксис.

n – это количество элементов, которые функция получает в качестве входов. Таким образом, в данном примере для n входов ее сложность равна n 2 .

Сравнение общепринятых обозначений.

n	Постоянная O(1)	Логарифмическая O(log n)	Линейная O(n)	Линейный логарифмический O(n log n)	Квадратичный O(n 2	Кубический O(n 3 )
1	1	1	1	1	1	1
2	1	1	2	1	4	8
4	1	2	4	8	16	64
8	1	3	8	24	64	512
16	1	4	16	64	256	4,096
1,024	1	10	1,024	10,240	1,048,576	1,073,741,824

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

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

O(1)

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

O(n)

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

O(n 2 )

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

O(2 n )

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

O(log n)

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

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

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