Что такое алгоритмическая сложность?

Что такое алгоритмическая сложность?

Алгоритмическая сложность (или complexity) — это мера того, как количество операций в алгоритме растёт с увеличением входных данных. Это помогает оценить, насколько быстро будет работать программа при увеличении объёма данных.

Высокая алгоритмическая сложность означает медленное выполнение на больших наборах данных. Низкая сложность означает быстрое выполнение даже на больших наборах.

Почему это важно для Frontend?

Хотя Frontend часто работает с меньшими объёмами данных, алгоритмическая сложность критична для:

• Обработки больших списков (React списки с 1000+ элементов)
• Поиска и фильтрации
• Сортировки данных
• Манипуляции с DOM
• Производительности веб-приложений

Big O нотация

Big O — это стандартный способ описания алгоритмической сложности. Основные типы (от лучшего к худшему):

O(1)      // Константная сложность
O(log n)  // Логарифмическая
O(n)      // Линейная
O(n log n)// Линейно-логарифмическая
O(n²)     // Квадратичная
O(n³)     // Кубическая
O(2^n)    // Экспоненциальная
O(n!)     // Факториальная

1. O(1) — Константная сложность

Время выполнения НЕ зависит от размера входных данных.

function getFirstElement(arr) {
  return arr[0]; // Всегда 1 операция
}

function add(a, b) {
  return a + b; // Всегда 1 операция
}

// В React: доступ к объекту
const user = users[0]; // O(1)

Примеры: доступ к элементу по индексу, чтение переменной, математическая операция.

2. O(log n) — Логарифмическая сложность

Время растёт логарифмически. При увеличении данных в 2 раза, операции увеличиваются на 1.

// Бинарный поиск
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;
}

// Поиск в отсортированном массиве из 1000 элементов
// потребует примерно log₂(1000) ≈ 10 проверок

Примеры: бинарный поиск, поиск в BST (Binary Search Tree).

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

Время растёт пропорционально размеру входных данных.

function findMax(arr) {
  let max = arr[0];
  
  // Проходим по всем элементам один раз
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i];
  }
  
  return max; // O(n)
}

// React: рендер списка
function UsersList({ users }) {
  return (
    <ul>
      {users.map(user => (  // O(n) - render каждого пользователя
        <li key={user.id}>{user.name}</li>
      ))}
    </ul>
  );
}

Примеры: линейный поиск, фильтрация, рендер списка.

4. O(n log n) — Линейно-логарифмическая

Средняя сложность хороших алгоритмов сортировки.

// Merge Sort
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // O(log n) уровней
  const right = mergeSort(arr.slice(mid));      // O(n) операций на уровне
  
  return merge(left, right); // Итого: O(n log n)
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i), right.slice(j));
}

// const sorted = mergeSort([3, 1, 4, 1, 5, 9]);

Примеры: сортировка (merge sort, quick sort), эффективные алгоритмы поиска.

5. O(n²) — Квадратичная сложность

Время растёт в квадрате. Очень медленно для больших данных.

// Bubble Sort - ПЛОХОЙ алгоритм сортировки
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {  // Вложенный цикл!
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr; // O(n²)
}

// Проверка всех пар элементов
function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {  // O(n²)
      if (arr[i] === arr[j]) return true;
    }
  }
  return false;
}

Примеры: bubble sort, вложенные циклы, проверка всех пар.

6. O(2^n) — Экспоненциальная сложность

Очень медленная, практически неиспользуемая для больших данных.

// Простая рекурсия для чисел Фибоначчи - ПЛОХОЙ подход
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2); // O(2^n)
}

// fibonacci(50) вычисляется вечность!

// Лучше с мемоизацией: O(n)
function fibonacciMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n <= 1) return n;
  
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

Практическое сравнение

// Сравнение для n = 1000 элементов:

O(1)       ->  1 операция
O(log n)   ->  ~10 операций
O(n)       ->  1000 операций
O(n log n) ->  ~10000 операций
O(n²)      ->  1000000 операций  // Медленно!
O(2^n)     ->  бесконечность     // Невозможно!

Пространственная сложность (Space Complexity)

Так же важна память, которую использует алгоритм:

// O(1) пространства - in-place сортировка
function sort(arr) {
  // Сортируем сам массив, не создаём новых
  for (let i = 0; i < arr.length; i++) {
    // ...
  }
}

// O(n) пространства - создаём новый массив
function sortNonMutating(arr) {
  const sorted = [...arr]; // Новый массив O(n)
  // Сортируем sorted
  return sorted;
}

Реальные примеры в Frontend

// ПЛОХО: O(n²) поиск в списке
function findUser(users, id) {
  for (let i = 0; i < users.length; i++) {
    for (let j = 0; j < users[i].posts.length; j++) {
      if (users[i].posts[j].id === id) return users[i];
    }
  }
}

// ХОРОШО: O(n) с использованием Map
function createUserIndex(users) {
  const index = new Map();
  for (const user of users) {
    for (const post of user.posts) {
      index.set(post.id, user);
    }
  }
  return index;
}
const user = userIndex.get(id); // O(1)

// ОЧЕНЬ ХОРОШО: Используем database индексы
// SELECT * FROM users WHERE posts.id = ?

Как оптимизировать сложность

// 1. Используй правильные структуры данных
const set = new Set(arr);        // O(1) поиск вместо O(n)
const map = new Map(arr);        // O(1) доступ вместо O(n)

// 2. Используй встроенные методы (оптимизированные)
const sorted = arr.sort();       // O(n log n)

// 3. Избегай вложенных циклов
for (let i = 0; i < n; i++) {   // O(n²) - ПЛОХО
  for (let j = 0; j < n; j++) { 
    // ...
  }
}

// 4. Используй кэширование/мемоизацию
const cache = {};
function expensive(n) {
  if (n in cache) return cache[n];
  const result = /* вычисления */;
  cache[n] = result;
  return result;
}

Вывод

Алгоритмическая сложность — это не просто теория, это практический инструмент для написания быстрых приложений. При разработке Frontend:

• Всегда думай о сложности при работе с большими списками
• Используй правильные структуры данных (Set, Map вместо массивов)
• Избегай вложенных циклов где возможно
• Профилируй реальное приложение (DevTools Performance tab)
• Оптимизируй медленные операции после обнаружения узких мест