Что такое линейная сложность? Чему соответствует O(n)?

Что такое линейная сложность O(n)?

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

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

Самый простой пример — поиск элемента в неотсортированном массиве (линейный поиск). Алгоритм проходит по каждому элементу, пока не найдет нужный. В худшем случае (если элемента нет) он проверит все n элементов.

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}

Другие примеры: подсчет суммы элементов массива, нахождение максимального значения, копирование массива.

Как отличить O(n) от других сложностей?

• O(1) — константная сложность, время не зависит от n (например, доступ по индексу массива).
• O(log n) — логарифмическая сложность (бинарный поиск).
• O(n^2) — квадратичная сложность (вложенные циклы).

Линейная сложность — это золотая середина: она хуже константной, но лучше квадратичной. На практике O(n) часто является приемлемой для задач, где n не слишком велико (до миллионов элементов).

Вывод

Понимание O(n) необходимо для оценки производительности алгоритмов, особенно при работе с большими объемами данных. Линейная сложность встречается повсеместно: от простых циклов до обработки списков и файлов. Знание этой концепции помогает выбирать эффективные решения и избегать излишне медленных алгоритмов.