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

Определение

Линейно-логарифмическая сложность возникает когда алгоритм комбинирует перебор всех элементов (n) с логарифмическим разделением задачи (log n).

Формула

$O(n\log n)=O(n\cdot {\log }_{2}n)$

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

• Оптимальная сложность для сортировки сравнениями
• Медленнее чем O(n), но быстрее чем O(n²)
• Типична для алгоритмов “разделяй и властвуй”
• Хорошо масштабируется

Визуализация Merge Sort

Исходный массив: [38, 27, 43, 3]

Разделение:
            [38, 27, 43, 3]        <- уровень 0
           /              \
      [38, 27]          [43, 3]     <- уровень 1
       /    \            /    \
     [38]  [27]        [43]   [3]    <- уровень 2

Слияние:
     [38]  [27]        [43]   [3]    <- уровень 2
       \    /            \    /
      [27, 38]          [3, 43]     <- уровень 1
           \              /
            [3, 27, 38, 43]         <- уровень 0

Количество уровней: log₂(4) = 2
Операций на каждом уровне: n = 4
Итого: n × log n = 4 × 2 = 8 операций

Дерево разделения для n=8

Уровень 0:  [8 элементов]                          <- 8 операций
                  /            \
Уровень 1:     [4]            [4]                   <- 8 операций
              /   \          /   \
Уровень 2:  [2]   [2]      [2]   [2]                <- 8 операций
            / \   / \      / \   / \
Уровень 3: [1][1][1][1]  [1][1][1][1]               <- 8 операций

Высота дерева: log₂(8) = 3
Работа на каждом уровне: n = 8
Итого: 3 × 8 = 24 операции = 8 × log₂(8)

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

Размер (n)	n	n log₂ n	n²
10	10	33	100
100	100	664	10,000
1,000	1,000	9,966	1,000,000
10,000	10,000	132,877	100,000,000

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

Операции
      |
100K  |                                    ●  O(n²)
      |                                  ●
 75K  |                                ●
      |                              ●
 50K  |                            ●
      |                          ●
 25K  |                      ● ●
      |                 ● ●         O(n log n)
 10K  |          ● ● ●
      |    ● ● ●  O(n)
   0  +----------------------------------------------->
        10   100    1K     10K    100K           n

Почему O(n log n) оптимальна для сортировки?

Математически доказано, что любой алгоритм сортировки, основанный на сравнениях, не может работать быстрее чем O(n log n) в худшем случае.

Интуиция:

• Нужно сделать log n уровней разделения
• На каждом уровне обработать все n элементов
• Итого: n × log n операций

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

• Эффективные алгоритмы сортировки
• Построение индексов в базах данных
• Операции с приоритетными очередями
• Некоторые задачи на графах
• Обработка больших объемов данных

Алгоритмы с O(n log n)

Алгоритм	Лучший случай	Средний случай	Худший случай
Merge Sort	O(n log n)	O(n log n)	O(n log n)
Quick Sort	O(n log n)	O(n log n)	O(n²)
Heap Sort	O(n log n)	O(n log n)	O(n log n)
Tim Sort	O(n)	O(n log n)	O(n log n)

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

✅ Оптимально для сортировки сравнениями ✅ Хорошо масштабируется на больших данных ✅ Стабильная производительность ❌ Медленнее линейных алгоритмов ❌ Требует дополнительной памяти (Merge Sort)

Примеры кода

1. Сортировка слиянием (Merge Sort)

function mergeSort(arr) {
  // Базовый случай
  if (arr.length <= 1) {
    return arr;
  }
 
  // Разделяем массив пополам
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
 
  // Рекурсивно сортируем половины
  return merge(mergeSort(left), mergeSort(right));
}
 
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)).concat(right.slice(j));
}
 
const arr = [38, 27, 43, 3, 9, 82, 10];
console.log(mergeSort(arr)); // [3, 9, 10, 27, 38, 43, 82]

2. Быстрая сортировка (Quick Sort)

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
 
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
 
  return [...quickSort(left), ...middle, ...quickSort(right)];
}
 
const arr = [10, 7, 8, 9, 1, 5];
console.log(quickSort(arr)); // [1, 5, 7, 8, 9, 10]

3. Пирамидальная сортировка (Heap Sort)

function heapSort(arr) {
  const n = arr.length;
 
  // Построение кучи
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(arr, n, i);
  }
 
  // Извлечение элементов из кучи
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }
 
  return arr;
}
 
function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
 
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }
 
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }
 
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

4. Сортировка + проход

function findDuplicatesEfficient(arr) {
  // Сортировка - O(n log n)
  const sorted = [...arr].sort((a, b) => a - b);
 
  // Один проход - O(n)
  const duplicates = [];
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i] === sorted[i - 1] && 
        !duplicates.includes(sorted[i])) {
      duplicates.push(sorted[i]);
    }
  }
 
  // Итого: O(n log n) + O(n) = O(n log n)
  return duplicates;
}