Что означает нотация O(n) (О-большое от n)?

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

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

Классический пример — линейный поиск в массиве:

// Функция поиска индекса элемента в массиве.
// В худшем случае (элемента нет) она проверит все n элементов.
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) { // Цикл от 0 до n-1 -> O(n) операций
        if (arr[i] === target) {
            return i; // Найденный индекс
        }
    }
    return -1; // Элемент не найден
}

// Пример вызова:
const numbers = [5, 2, 9, 1, 5, 6]; // n = 6
console.log(linearSearch(numbers, 1)); // Пройдет ~3 итерации (лучший/средний случай)
console.log(linearSearch(numbers, 10)); // Пройдет все 6 итераций (худший случай, O(n))

Важные нюансы нотации "О-большое":

1. Анализ худшего случая: O(n) описывает верхнюю границу роста в худшем сценарии.
2. Игнорирование констант и младших слагаемых: Константные множители и слагаемые меньшего порядка отбрасываются. Алгоритмы со сложностью O(2n + 100) и O(n/3) упрощаются до O(n), так как при очень больших n именно линейный рост n будет определять поведение.
3. Не только время: Нотация также применяется для оценки пространственной сложности (потребления памяти). Например, создание нового массива размером n будет иметь пространственную сложность O(n).

Другие примеры алгоритмов с O(n):

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

Понимание O(n) и других асимптотических сложностей (O(1), O(log n), O(n²)) критически важно для выбора оптимального алгоритма при работе с большими объемами данных.