Что означает сложность алгоритма O(n)? Приведите примеры разных сложностей.?

Что такое O(n) и асимптотическая сложность

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

Нотация O-большое описывает верхнюю границу роста времени выполнения (или потребления памяти) при увеличении объема входных данных. Она игнорирует константные множители и менее значимые слагаемые, фокусируясь на асимптотическом поведении при больших n.

Пример алгоритма с O(n)

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

function findMax(array $arr): int {
    $max = $arr[0]; // O(1)
    $n = count($arr); // O(1)
    
    for ($i = 1; $i < $n; $i++) { // Цикл выполнится n-1 раз
        if ($arr[$i] > $max) { // O(1) внутри цикла
            $max = $arr[$i]; // O(1)
        }
    }
    
    return $max; // O(1)
}

// Время выполнения: O(1) + O(1) + (n-1)*O(1) + O(1) = O(n)

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

Примеры других распространенных сложностей

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

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

function getFirstElement(array $arr) {
    return $arr[0] ?? null; // Всегда одна операция
}

Примеры в реальности: доступ к элементу массива по индексу, вставка/удаление в конце массива (амортизированно), работа с хеш-таблицами в лучшем случае.

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

Время выполнения растет логарифмически относительно размера входных данных. Очень эффективно для больших данных.

function binarySearch(array $sortedArr, int $target): int {
    $left = 0;
    $right = count($sortedArr) - 1;
    
    while ($left <= $right) {
        $mid = (int)(($left + $right) / 2);
        
        if ($sortedArr[$mid] === $target) {
            return $mid;
        }
        
        if ($sortedArr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    return -1;
}

Примеры в реальности: бинарный поиск, операции в сбалансированных деревьях поиска (AVL, красно-черные), некоторые алгоритмы "разделяй и властвуй".

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

Характерна для эффективных алгоритмов сортировки.

// Пример слияния в MergeSort (упрощенно)
function mergeSort(array $arr): array {
    $n = count($arr);
    if ($n <= 1) return $arr;
    
    $mid = (int)($n / 2);
    $left = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    
    return merge($left, $right); // Слияние за O(n)
}

Примеры в реальности: быстрая сортировка (в среднем), сортировка слиянием, сортировка кучей. Это "стандарт" для алгоритмов сортировки сравнением.

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

Время выполнения пропорционально квадрату размера входных данных.

function bubbleSort(array $arr): array {
    $n = count($arr);
    
    for ($i = 0; $i < $n; $i++) { // n итераций
        for ($j = 0; $j < $n - $i - 1; $j++) { // В среднем ~n/2 итераций
            if ($arr[$j] > $arr[$j + 1]) {
                // Меняем элементы местами
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    
    return $arr;
}
// Общее время: O(n * n/2) = O(n²)

Примеры в реальности: пузырьковая сортировка, сортировка выбором, некоторые наивные алгоритмы поиска пар элементов.

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

Время выполнения растет экспоненциально. Такие алгоритмы становятся непрактичными даже для относительно небольших n.

function fibonacciRecursive(int $n): int {
    if ($n <= 1) return $n;
    return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2);
}
// Каждый вызов порождает 2 новых вызова: O(2ⁿ)

Примеры в реальности: наивная рекурсивная реализация чисел Фибоначчи, задача коммивояжера полным перебором, некоторые задачи на подмножества.

O(n!) — Факториальная сложность

Самая медленная из распространенных сложностей. Характерна для задач полного перебора всех перестановок.

function generatePermutations(array $items, array $current = []): array {
    if (empty($items)) {
        return [$current];
    }
    
    $permutations = [];
    foreach ($items as $i => $item) {
        $remaining = $items;
        array_splice($remaining, $i, 1);
        $permutations = array_merge(
            $permutations,
            generatePermutations($remaining, array_merge($current, [$item]))
        );
    }
    
    return $permutations;
}
// Для n элементов будет n! перестановок

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

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

Понимание сложности алгоритмов критически важно для backend-разработчика:

• Выбор алгоритмов: для больших данных O(n²) может быть неприемлемым, тогда как O(n log n) — работоспособным
• Оптимизация: поиск "узких мест" в производительности часто начинается с анализа сложности алгоритмов
• Прогнозирование масштабируемости: как будет вести себя система при увеличении данных в 10, 100, 1000 раз
• Проектирование API: понимание, какие операции могут быть дорогими и требуют кэширования или иной оптимизации

В реальных PHP-приложениях чаще всего встречаются алгоритмы со сложностью O(1), O(log n), O(n) и O(n log n). Алгоритмы с O(n²) и выше обычно требуют рефакторинга или использования более оптимальных подходов при работе с производственными объемами данных.