Что такое алгоритм и сложность? Big O для людей

Алгоритм — это не страшная математика из учебника. Это просто чёткий набор шагов для решения задачи. В этом уроке мы разберёмся, почему алгоритмы важны и как оценивать их эффективность с помощью нотации Big O — без формул и слёз.

🗺️ Что такое алгоритм

Слово «алгоритм» звучит серьёзно и научно. На самом деле вы используете алгоритмы каждый день, просто не называете их так.

Рецепт приготовления пасты — это алгоритм. Инструкция по сборке мебели из IKEA — алгоритм. Маршрут «дом → работа» — тоже алгоритм. Общее у них одно: конкретная последовательность шагов, которая берёт входные данные и даёт результат.

В программировании алгоритмы — это способы решать типовые задачи: отсортировать массив, найти элемент, обойти граф, сжать данные. Хороший программист знает не просто как решить задачу, но и насколько эффективно.

Возьмём простой пример. Задача: найти имя «Алёна» в списке контактов из 1000 человек.

Разница — в 100 раз! И это для 1000 элементов. На миллионе данных разница станет катастрофической: плохой алгоритм будет работать секунды или минуты там, где хороший справляется мгновенно.

💡 Зачем это нужно программисту

Может показаться, что алгоритмы — это академическая история, далёкая от реальной работы. Это не так. Вот несколько ситуаций из жизни, когда знание алгоритмов спасает проект.

И даже если вы пишете небольшое приложение — знание алгоритмов помогает думать о коде правильно: не делать лишней работы, избегать вложенных циклов там, где они не нужны, выбирать подходящие структуры данных.

📐 Big O: как измеряют скорость алгоритма

Когда программисты говорят «этот алгоритм быстрее», им нужна общая система измерения. Нельзя просто сказать «10 миллисекунд» — на вашем компьютере будет одно, на старом телефоне другое. Нужна метрика, которая не зависит от железа.

Big O (нотация «О большого») — это способ описать, как растёт время работы алгоритма при увеличении входных данных. Мы смотрим не на конкретное время, а на тенденцию: если данных стало в 10 раз больше, насколько медленнее стал алгоритм?

Давайте разберём четыре самые важные сложности: O(1), O(n), O(n²) и O(log n). Запомните их — и вы будете говорить на языке алгоритмов.

⚡ O(1) — Константное время

O(1) означает, что алгоритм выполняется за одинаковое время независимо от размера входных данных. Нет входных данных 10, или 10 000, или 10 миллионов — разницы нет.

Аналогия: вы знаете номер своего шкафчика в раздевалке. Чтобы найти его, не нужно проверять все шкафчики — вы идёте прямо к нужному. 100 шкафчиков или 10 000 — вам всё равно нужен один шаг.

// O(1) — получить первый элемент массива
function getFirst(arr) {
  return arr[0]; // всегда один шаг, неважно какой длины массив
}

// O(1) — проверка значения по ключу в объекте (хеш-таблице)
const prices = { apple: 50, banana: 30, mango: 120 };
console.log(prices["mango"]); // мгновенно, 3 позиции или 3 000 000 — без разницы

Доступ по индексу к массиву, чтение по ключу из объекта/Map — это классические примеры O(1). Это идеальная сложность.

📈 O(n) — Линейное время

O(n) означает, что время растёт пропорционально количеству данных. В 10 раз больше данных — в 10 раз дольше работает. Это интуитивно понятная сложность.

Аналогия: нужно пожать руку каждому на вечеринке. 10 гостей — 10 рукопожатий. 100 гостей — 100 рукопожатий. Количество действий равно количеству людей.

// O(n) — простой цикл по всему массиву
function findMax(arr) {
  let max = arr[0];
  for (let i = 1; i < arr.length; i++) { // n итераций
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  return max;
}

// O(n) — линейный поиск
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) { // в худшем случае — n шагов
    if (arr[i] === target) return i;
  }
  return -1;
}

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

🐢 O(n²) — Квадратичное время

O(n²) — это когда время растёт как квадрат от размера данных. В 10 раз больше данных — в 100 раз дольше. В 100 раз больше данных — в 10 000 раз дольше!

Аналогия: на вечеринке нужно познакомить каждого гостя с каждым. 10 гостей — 100 знакомств. 100 гостей — 10 000 знакомств. Масштабируется ужасно.

Классический признак O(n²) — вложенный цикл: цикл внутри цикла, оба по n элементов.

// O(n²) — вложенный цикл: сравниваем каждую пару
function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {        // n итераций
    for (let j = i + 1; j < arr.length; j++) {  // n итераций (вложенный!)
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

// Это O(n²) — пузырьковая сортировка (подробнее в уроке 11.3)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {         // внешний цикл
    for (let j = 0; j < arr.length - i - 1; j++) { // внутренний цикл
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

🚀 O(log n) — Логарифмическое время

O(log n) — один из самых быстрых классов. Время растёт очень медленно: данных стало в 10 раз больше, а шагов добавилось лишь немного. Это магия!

Аналогия: угадать число от 1 до 1024, задавая вопросы «больше или меньше?». Каждый ответ отсекает половину вариантов. 1024 → 512 → 256 → ... За 10 вопросов — точный ответ!

Именно так работает бинарный поиск — он каждый шаг делит задачу пополам. Подробно разберём его в уроке 11.6.

// O(log n) — бинарный поиск (предварительный вид, детали в уроке 11.6)
function binarySearch(sortedArr, target) {
  let left = 0;
  let right = sortedArr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (sortedArr[mid] === target) return mid;
    if (sortedArr[mid] < target) left = mid + 1; // отсекаем левую половину
    else right = mid - 1;                         // отсекаем правую половину
  }

  return -1;
}

// 1 000 000 элементов → максимум ~20 шагов!
// log₂(1 000 000) ≈ 20

📊 Как растёт время: наглядная таблица

Допустим, один шаг алгоритма занимает 1 мс. Посмотрим, сколько времени займут разные алгоритмы при разном количестве данных.

Видите? O(n²) при миллионе элементов работает 32 года. Это не опечатка. Именно поэтому выбор алгоритма — это не академический вопрос, а вполне прикладной.

🗂️ Четыре сложности: шпаргалка

✅ Итоги урока

• Алгоритм — это чёткий набор шагов для решения задачи с входными данными и результатом
• Выбор алгоритма критически влияет на производительность реальных приложений
• Big O описывает, как растёт время работы при увеличении данных — независимо от железа
• O(1) — константное: время не зависит от данных (доступ по индексу, ключу)
• O(log n) — логарифмическое: делим задачу пополам (бинарный поиск)
• O(n) — линейное: один проход по всем данным (простой цикл)
• O(n²) — квадратичное: цикл в цикле, на больших данных — катастрофа
• Один миллион элементов: O(log n) = 20 шагов, O(n²) = 32 года