Что такое O(n)?

Что такое O(n) в контексте алгоритмов?

O(n) — это обозначение линейной временной сложности (Big O notation) в анализе алгоритмов. Оно описывает, как время выполнения алгоритма растёт пропорционально размеру входных данных n. Если кратко: при увеличении n в k раз, время выполнения также увеличится примерно в k раз (в худшем или среднем случае). Это фундаментальное понятие в информатике для оценки эффективности кода.

Основные принципы O(n)

• Линейная зависимость: Алгоритм с O(n) выполняет операции над каждым элементом входных данных один раз (или постоянное количество раз). Например, поиск в неотсортированном массиве, где в худшем случае нужно проверить все n элементов.
• "О-большое" (Big O): Обозначение O(n) относится к асимптотической сложности, то есть описывает поведение алгоритма при стремлении n к бесконечности. Константные множители и младшие слагаемые игнорируются (например, O(2n + 5) упрощается до O(n)).
• Класс сложности: O(n) находится между константной сложностью O(1) (идеал) и квадратичной O(n²) (часто неэффективно для больших данных).

Примеры кода с O(n)

1. Поиск в массиве

/**
 * Линейный поиск элемента в массиве.
 * Сложность: O(n) — в худшем случае проверяем все n элементов.
 */
function linearSearch(array $arr, $target): int|false {
    for ($i = 0; $i < count($arr); $i++) {
        if ($arr[$i] === $target) {
            return $i; // Элемент найден
        }
    }
    return false; // Элемент отсутствует
}

// Пример использования
$array = [5, 3, 8, 1, 9];
$result = linearSearch($array, 8); // Найдет на 3-й итерации

2. Сумма элементов массива

/**
 * Вычисление суммы всех элементов.
 * Сложность: O(n) — обязательный однократный проход по всем n элементам.
 */
function arraySum(array $arr): int {
    $sum = 0;
    foreach ($arr as $value) {
        $sum += $value;
    }
    return $sum;
}

// Другой вариант с тем же O(n)
function arraySumAlt(array $arr): int {
    return array_reduce($arr, fn($carry, $item) => $carry + $item, 0);
}

3. Фильтрация данных (реализация filter)

/**
 * Фильтрация массива по условию.
 * Сложность: O(n) — проверяем условие для каждого из n элементов.
 */
function filterEvenNumbers(array $numbers): array {
    $result = [];
    foreach ($numbers as $num) {
        if ($num % 2 === 0) {
            $result[] = $num;
        }
    }
    return $result;
}

Важные уточнения

• O(n) ≠ "медленно": Для небольших данных или когда n гарантированно мало, O(n) может быть оптимальным выбором благодаря простоте реализации.
• "Скрытые" O(n) операции: Некоторые встроенные функции PHP имеют O(n), что важно учитывать в циклах:

  // Внешне O(n²), но из-за count($arr) на каждой итерации — фактически O(n²)
  for ($i = 0; $i < count($arr); $i++) { // count() — O(1) в PHP 7+, но в общем случае стоит выносить
      // ...
  }
  

• Пространственная сложность: O(n) может также относиться к использованию памяти (например, создание нового массива размером n).

Сравнение с другими классами сложности

Когда O(n) приемлемо или неизбежно?

1. Чтение/запись всех данных: Если алгоритм по определению должен обработать каждый входной элемент (например, загрузка файла, валидация всех записей).
2. Однопроходные алгоритмы: Задачи, где данные можно обработать за один проход без хранения всего в памяти (stream processing).
3. Предварительная обработка: O(n) может быть этапом для более эффективных последующих операций (например, построение хеш-таблицы за O(n) для последующих поисков за O(1)).

Вывод: O(n) — это базовый и предсказуемый класс сложности. Понимание, где ваш код имеет линейную сложность, критически важно для написания эффективных приложений, особенно при работе с большими объёмами данных. В PHP-разработке это особенно актуально при обработке массивов, работе с базами данных (где n — количество записей) и парсинге больших документов.