Нотация Big O

11.1 Определение нотации Big O

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

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

Основные нотации:

O(1) — Константная сложность:

• Время выполнения алгоритма не зависит от размера входных данных.
• Пример: доступ к элементу массива по индексу.

O(n) — Линейная сложность:

• Время выполнения алгоритма линейно зависит от размера входных данных.
• Пример: простой перебор всех элементов массива.

O(log n) — Логарифмическая сложность:

• Время выполнения алгоритма растёт логарифмически с увеличением размера входных данных.
• Пример: бинарный поиск в отсортированном массиве.

O(n^2) — Квадратичная сложность:

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

O(2^n) — Экспоненциальная сложность:

• Время выполнения алгоритма экспоненциально зависит от размера входных данных.
• Пример: решение задачи о рюкзаке полным перебором.

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

11.2 Интерпретация нотации Big O

Как интерпретировать и использовать нотацию Big O?

Игнорирование констант и менее значимых членов: Big O описывает порядок роста функции, игнорируя константы и менее значимые члены. Например, O(2n) и O(3n) интерпретируются как O(n).

Сравнение алгоритмов: Big O позволяет сравнивать алгоритмы по их асимптотической эффективности. Например, алгоритм с O(n log n) эффективнее, чем алгоритм с O(n^2) для очень больших объёмов данных.

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

Игнорирование констант

Рассмотрим примеры игнорирования констант и менее значимых членов:

Пример 1. Рассмотрим две функции:

• f(n) = 3n + 2
• g(n) = 5n + 1

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

Пример 2. Рассмотрим две функции:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

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

11.3 Сравнение алгоритмов

1. Сравнение алгоритмов на очень больших объёмах данных

Пример 1:

• Алгоритм A имеет временную сложность O(n^2).
• Алгоритм B имеет временную сложность O(n log n).

Для малых значений n алгоритм A может работать быстрее из-за меньших констант, но для больших значений n алгоритм B будет значительна быстрее, так как его рост логарифмический, а не квадратичный.

Пример 2:

• Алгоритм X имеет временную сложность O(n).
• Алгоритм Y имеет временную сложность O(1).

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

2. Анализ худшего случая

Пример 1:

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

Пример 2:

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

3. Влияние на производительность и масштабируемость

Пример 1:

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

• Алгоритм с O(n^2) будет выполнять приблизительно 100 000 000 операций для 10 000 элементов.
• Алгоритм с O(n log n) будет выполнять около 40 000 операций для 10 000 элементов.

Пример 2:

Рассмотрим алгоритм, который работает за O(2^n). Если мы увеличиваем размер входных данных с 10 до 20 элементов, количество операций возрастает экспоненциально.

• Для n = 10: 2^10 = 1 024 операций.
• Для n = 20: 2^20 = 1 048 576 операций.

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