Просмотр исходного текста страницы Нотация "O" (Big O notation)

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

== Основные понятия ==

# '''Временная сложность''': Описывает, как время выполнения алгоритма растет с увеличением размера входных данных.
# '''Пространственная сложность''': Описывает, как объем используемой памяти алгоритмом растет с увеличением размера входных данных.

== Формальное определение ==

Функция $f(n)$ имеет порядок $O(g(n))$, если существуют положительные константы $c$ и $n_0$ такие, что для всех $n > n_0$ выполняется неравенство:
$$ 0 \le f(n) \le c \cdot g(n) $$

Это означает, что $f(n)$ растет не быстрее, чем $g(n)$ с точностью до постоянного множителя $c$, начиная с некоторого значения $n_0$.

== Распространенные классы сложности ==

# '''O(1)''': Константная сложность. Время выполнения не зависит от размера входных данных.

## Пример: Доступ к элементу массива по индексу.
# '''O(log n)''': Логарифмическая сложность. Время выполнения растет логарифмически с увеличением размера входных данных.

## Пример: Бинарный поиск в отсортированном массиве.
# '''O(n)''': Линейная сложность. Время выполнения растет линейно с увеличением размера входных данных.

## Пример: Линейный поиск в массиве.
# '''O(n log n)''': Линейно-логарифмическая сложность.

## Пример: Быстрая сортировка (в среднем случае), сортировка слиянием.
# '''O(n^2)''': Квадратичная сложность. Время выполнения растет квадратично с увеличением размера входных данных.

## Пример: Сортировка выбором, сортировка пузырьком.
# '''O(n^3)''': Кубическая сложность. Время выполнения растет кубически с увеличением размера входных данных.

## Пример: Умножение матриц.
# '''O(2^n)''': Экспоненциальная сложность. Время выполнения растет экспоненциально с увеличением размера входных данных.

## Пример: Решение задачи коммивояжера методом перебора.
# '''O(n!)''': Факториальная сложность. Время выполнения растет факториально с увеличением размера входных данных.

## Пример: Генерация всех перестановок элементов массива.

== Примеры и объяснения ==

# '''O(1) - Константная сложность''':
## Если алгоритм всегда выполняет одну и ту же операцию, независимо от размера входных данных, то его сложность $O(1)$.
## ```javascript
## function getFirstElement(arr) {
##     return arr[0];
## }
## ```
# '''O(n) - Линейная сложность''':
## Если алгоритм должен пройти через каждый элемент входных данных один раз, то его сложность $O(n)$.
## ```javascript
## function findElement(arr, target) {
##     for (let i = 0; i < arr.length; i++) {
##         if (arr[i] === target) {
##             return i;
##         }
##     }
##     return -1;
## }
## ```
# '''O(n^2) - Квадратичная сложность''':
## Если алгоритм должен пройти через все пары элементов во входных данных, то его сложность $O(n^2)$.
## ```javascript
## function compareAllPairs(arr) {
##     for (let i = 0; i < arr.length; i++) {
##         for (let j = 0; j < arr.length; j++) {
##             console.log(arr[i], arr[j]);
##         }
##     }
## }
## ```
# '''O(log n) - Логарифмическая сложность''':
## Если алгоритм уменьшает размер входных данных вдвое на каждом шаге, то его сложность $O(\log n)$.
## ```javascript
## function binarySearch(arr, target) {
##     let left = 0;
##     let right = arr.length - 1;
##     while (left <= right) {
##         let mid = Math.floor((left + right) / 2);
##         if (arr[mid] === target) return mid;
##         if (target < arr[mid]) right = mid - 1;
##         else left = mid + 1;
##     }
##     return -1;
## }
## ```

== Правила упрощения ==

# '''Правило доминирования''': Если функция представляет собой сумму нескольких слагаемых, то учитывается только слагаемое с наибольшим порядком роста.
## Пример: $O(n^2 + n) = O(n^2)$
# '''Правило умножения констант''': Постоянные множители игнорируются.
## Пример: $O(5n) = O(n)$
# '''Правило суммирования последовательностей''': Если алгоритм состоит из последовательности шагов, то общая сложность определяется шагом с наибольшей сложностью.

== Практическое значение ==

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

== Важные замечания ==

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