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

Определение

Логарифмическая сложность означает, что на каждой итерации размер обрабатываемых данных уменьшается в несколько раз (обычно вдвое).

Формула

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

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

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

• Очень эффективная сложность
• Размер задачи уменьшается на каждом шаге
• Работает по принципу “разделяй и властвуй”
• Растет очень медленно

Визуализация бинарного поиска

Массив из 16 элементов (ищем 13):
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

Шаг 1: [1...........................16]  -> проверяем 8
                    ^

Шаг 2:              [9..............16]  -> проверяем 12
                         ^

Шаг 3:                   [13.......16]  -> проверяем 14
                            ^

Шаг 4:                   [13..14]       -> проверяем 13 ✓
                          ^

Итого: 4 шага для 16 элементов = log₂(16) = 4

Визуализация деления пополам

1024 -> 512 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1

Количество шагов: 10 = log₂(1024)

Каждый шаг уменьшает задачу вдвое!

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

Размер данных (n)	Операций (log₂ n)	Время
10	3	~3 мс
100	7	~7 мс
1,000	10	~10 мс
1,000,000	20	~20 мс
1,000,000,000	30	~30 мс

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

Операции
    |
 30 |                                    ●  O(n)
    |                                  ●
 25 |                                ●
    |                              ●
 20 |                            ●
    |                          ●
 15 |                        ●
    |                      ●
 10 |                    ●   O(log n)
    |            ● ● ● ●
  5 |    ● ● ● ●
    | ●●●
  0 +-------------------------------------------->
    10   100   1K    10K   100K   1M        n

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

• Бинарный поиск
• Сбалансированные деревья (AVL, Red-Black)
• Поиск в словарях
• Системы управления базами данных (индексы)
• Алгоритмы разделяй-и-властвуй

Ключевое свойство

При увеличении n в 1000 раз, log n увеличится примерно в 3 раза!

• log₂(1000) ≈ 10
• log₂(1000000) ≈ 20

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

✅ Требуется отсортированная структура данных ✅ Очень эффективна для больших объемов ✅ Уменьшает задачу вдвое на каждом шаге ❌ Не работает на неотсортированных данных

Примеры кода

1. Бинарный поиск

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
 
    if (arr[mid] === target) {
      return mid; // Элемент найден
    }
 
    if (arr[mid] < target) {
      left = mid + 1; // Ищем в правой половине
    } else {
      right = mid - 1; // Ищем в левой половине
    }
  }
 
  return -1; // Элемент не найден
}
 
// Пример использования
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
console.log(binarySearch(sortedArray, 13)); // 6

2. Поиск в бинарном дереве поиска

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}
 
function searchBST(root, target) {
  if (!root) return null;
 
  if (root.value === target) {
    return root;
  }
 
  if (target < root.value) {
    return searchBST(root.left, target); // Ищем в левом поддереве
  } else {
    return searchBST(root.right, target); // Ищем в правом поддереве
  }
}

3. Алгоритм Евклида (НОД)

function gcd(a, b) {
  while (b !== 0) {
    const temp = b;
    b = a % b;
    a = temp;
  }
  return a;
}
 
console.log(gcd(48, 18)); // 6

4. Поиск в отсортированной матрице

function searchMatrix(matrix, target) {
  let left = 0;
  let right = matrix.length * matrix[0].length - 1;
 
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const row = Math.floor(mid / matrix[0].length);
    const col = mid % matrix[0].length;
    const midValue = matrix[row][col];
 
    if (midValue === target) return true;
    if (midValue < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
 
  return false;
}