O(n) — Линейная сложность

Определение

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

Формула

$O(n)$

где $n$ — размер входных данных

Характеристики

• Время выполнения растет линейно
• Каждый элемент обрабатывается один раз
• Если данных в 2 раза больше -> времени в 2 раза больше
• Хорошая эффективность для многих задач

Визуализация обхода массива

Массив: [10, 20, 30, 40, 50]

Проход по элементам:
Шаг 1: [10] -> обработали 1 элемент
Шаг 2: [10, 20] -> обработали 2 элемента
Шаг 3: [10, 20, 30] -> обработали 3 элемента
Шаг 4: [10, 20, 30, 40] -> обработали 4 элемента
Шаг 5: [10, 20, 30, 40, 50] -> обработали 5 элементов

Количество операций = n

Сравнение производительности

Размер данных (n)	Операций	Время
10	10	10 мс
100	100	100 мс
1,000	1,000	1 сек
10,000	10,000	10 сек
100,000	100,000	100 сек

График сложности

Операции
     |
1000 |                                ●
     |                             ●
 750 |                          ●
     |                       ●     O(n)
 500 |                    ●
     |                 ●
 250 |              ●
     |           ●
 100 |        ●
     |     ●
  10 |  ●
     |●
   0 +--------------------------------------------->
      10   100   250   500   750   1000        n

Линейный рост: прямая зависимость

n = 10  -> операций = 10    [●]
n = 20  -> операций = 20    [●●]
n = 30  -> операций = 30    [●●●]
n = 40  -> операций = 40    [●●●●]
n = 50  -> операций = 50    [●●●●●]
n = 100 -> операций = 100   [●●●●●●●●●●]

Множественные проходы

Если алгоритм делает несколько последовательных проходов, это все равно O(n):

function processArray(arr) {
  // Первый проход - O(n)
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
 
  // Второй проход - O(n)
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
 
  // Итого: O(n) + O(n) = O(2n) = O(n)
  return { sum, max };
}

O(n) + O(n) = O(2n) = O(n)

Константные множители отбрасываются!

Практическое применение

• Поиск элемента в неотсортированном массиве
• Обход всех элементов коллекции
• Подсчет статистики (сумма, среднее, максимум)
• Фильтрация данных
• Преобразование данных (map, filter)
• Копирование структур данных

Важно помнить

✅ Один проход по данным = O(n) ✅ Несколько последовательных проходов = O(n) ✅ Эффективно для умеренных объемов данных ❌ Для больших данных лучше искать O(log n) решения ❌ Вложенные циклы дают O(n²), не O(n)

Примеры кода

1. Линейный поиск

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i;
    }
  }
  return -1;
}
 
const numbers = [5, 3, 8, 1, 9, 2];
console.log(linearSearch(numbers, 9)); // 4

2. Поиск максимального элемента

function findMax(arr) {
  let max = arr[0];
 
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
 
  return max;
}
 
console.log(findMax([3, 7, 2, 9, 1])); // 9

3. Подсчет суммы элементов

function sum(arr) {
  let total = 0;
 
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
 
  return total;
}
 
console.log(sum([1, 2, 3, 4, 5])); // 15

4. Фильтрация массива

function filterEven(arr) {
  const result = [];
 
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] % 2 === 0) {
      result.push(arr[i]);
    }
  }
 
  return result;
}
 
console.log(filterEven([1, 2, 3, 4, 5, 6])); // [2, 4, 6]

5. Проверка на дубликаты (с Set)

function hasDuplicates(arr) {
  const seen = new Set();
 
  for (let i = 0; i < arr.length; i++) {
    if (seen.has(arr[i])) {
      return true;
    }
    seen.add(arr[i]);
  }
 
  return false;
}
 
console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 2, 5])); // true

6. Переворот строки

function reverseString(str) {
  let result = '';
 
  for (let i = str.length - 1; i >= 0; i--) {
    result += str[i];
  }
 
  return result;
}
 
console.log(reverseString('hello')); // 'olleh'

7. Обход связного списка

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
 
function printList(head) {
  let current = head;
 
  while (current !== null) {
    console.log(current.value);
    current = current.next;
  }
}

8. Копирование массива

function copyArray(arr) {
  const copy = [];
 
  for (let i = 0; i < arr.length; i++) {
    copy[i] = arr[i];
  }
 
  return copy;
}