Перейти на PRO

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

Тип вопроса: Алгоритмы и структуры данных Вероятность: 24% Категория: PHP Разработчик

Ответ

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²)) критически важно для выбора оптимального алгоритма при работе с большими объемами данных.

Ответ 18+ 🔞

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

Простыми словами: Увеличил кучу в 10 раз — в 10 раз дольше ищешь. Прямая связь, никакой магии.

Смотри на примере, как искать число в массиве:

// Ищешь число в списке. В худшем случае перелопатишь всё до последнего элемента.
function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) { // Этот цикл — и есть наше O(n). n раз крутится.
        if (arr[i] === target) {
            return i; // Ура, нашёл!
        }
    }
    return -1; // Проебался, такого числа нет.
}

// Пример:
const numbers = [5, 2, 9, 1, 5, 6]; // n = 6 элементов
console.log(linearSearch(numbers, 1)); // Повезло, нашёл быстро.
console.log(linearSearch(numbers, 10)); // А вот тут, бля, придётся проверить все 6. Это и есть худший случай O(n).

А теперь три главных пункта, которые все постоянно забывают:

  1. Худший сценарий: O(n) — это про то, как твой код обосрётся по полной. Когда будет искать носку, которой в куче вообще нет, и перероет всё.
  2. Константы — похуй. Если твой алгоритм делает не n, а, скажем, 2n + 100 операций, в большой нотации это всё равно O(n). Потому что когда n становится овердохуища большим, эти +100 и двойка — просто пыль. Рост всё равно линейный.
  3. Это не только про время. O(n) может быть и про память. Если ты создаёшь новый массив такого же размера, как входной, ты жрёшь памяти пропорционально n. Это пространственная сложность O(n).

Где ещё встречается? Да везде: найти максимум в списке, посчитать сумму, скопировать строку, прочитать все сообщения в чате — всё это, ёпта, линейные операции.

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

Видео-ответы

© ХакСобесов, 2026
support@hacksobesov.com