Что такое Big O и зачем это нужно знать?

Big O нотация — это способ описать, как быстро работает алгоритм при увеличении объема данных. Это один из самых важных концептов в программировании, который:

• 🎯 Спрашивают на каждом техническом собеседовании
• ⚡ Помогает выбирать эффективные решения
• 🔍 Позволяет сравнивать алгоритмы между собой
• 💡 Учит думать о производительности кода

Простая аналогия

Представьте, что вам нужно найти слово в словаре:

Способ 1: Читать каждое слово с начала — это O(n) Способ 2: Открыть примерно посередине и искать в нужной половине — это O(log n)

При 1000 слов первый способ потребует до 1000 проверок, второй — всего около 10.

Основные виды сложности

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

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

// Получение элемента по индексу — O(1)
function getFirst(array) {
    return array[0];
}

// Неважно, 10 элементов или 10 миллионов — одна операция
getFirst([1, 2, 3]);           // мгновенно
getFirst(hugeArrayOf10Million); // так же мгновенно

# То же на Python
def get_first(array):
    return array[0]

Примеры O(1):

• Доступ к элементу массива по индексу
• Добавление/удаление из начала или конца (push, pop)
• Получение значения из хеш-таблицы по ключу
• Математические операции

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

Время растет пропорционально количеству данных. В 2 раза больше данных = в 2 раза дольше.

// Поиск элемента в массиве — O(n)
function findElement(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i;
        }
    }
    return -1;
}

// 1000 элементов — до 1000 проверок
// 1 000 000 элементов — до 1 000 000 проверок

# То же на Python
def find_element(array, target):
    for i, item in enumerate(array):
        if item == target:
            return i
    return -1

Примеры O(n):

• Поиск элемента в несортированном массиве
• Подсчет суммы всех элементов
• Проверка, есть ли дубликаты (с Set)
• Один проход по массиву

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

Время растет как квадрат от количества данных. Вложенные циклы — типичный признак.

// Проверка всех пар — O(n²)
function findPairWithSum(array, target) {
    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {
            if (array[i] + array[j] === target) {
                return [i, j];
            }
        }
    }
    return null;
}

// 100 элементов — до 10 000 операций
// 1000 элементов — до 1 000 000 операций!

undefined

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

То же на Python

def find_pair_with_sum(array, target): for i in range(len(array)): for j in range(i + 1, len(array)): if array[i] + array[j] == target: return [i, j] return None

**Примеры O(n²):**
- Сортировка пузырьком
- Наивное решение Two Sum
- Проверка всех пар элементов
- Вложенные циклы по одному массиву

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

Очень эффективно! При каждом шаге отбрасывается половина данных.

```javascript
// Бинарный поиск — O(log n)
function binarySearch(sortedArray, target) {
    let left = 0;
    let right = sortedArray.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (sortedArray[mid] === target) {
            return mid;
        }

        if (sortedArray[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

// 1000 элементов — около 10 шагов
// 1 000 000 элементов — около 20 шагов!

# То же на Python
def binary_search(sorted_array, target):
    left, right = 0, len(sorted_array) - 1

    while left <= right:
        mid = (left + right) // 2

        if sorted_array[mid] == target:
            return mid
        elif sorted_array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

Примеры O(log n):

• Бинарный поиск
• Операции в сбалансированном дереве
• Поиск в отсортированном массиве

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

Типичная сложность эффективных сортировок.

// Сортировка слиянием — O(n log n)
function mergeSort(array) {
    if (array.length <= 1) return array;

    const mid = Math.floor(array.length / 2);
    const left = mergeSort(array.slice(0, mid));
    const right = mergeSort(array.slice(mid));

    return merge(left, 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));
}

Примеры O(n log n):

• Merge Sort, Quick Sort, Heap Sort
• Встроенные методы сортировки в языках
• Некоторые алгоритмы на графах

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

Очень медленно! Время удваивается при добавлении одного элемента.

// Наивный Фибоначчи — O(2ⁿ)
function fibonacci(n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// n = 10 — 1024 вызова
// n = 20 — более 1 000 000 вызовов
// n = 50 — не дождетесь результата!

Примеры O(2ⁿ):

• Наивная рекурсия без мемоизации
• Полный перебор всех подмножеств
• Некоторые задачи на рюкзак без оптимизации

Сравнительная таблица

Как определять сложность: пошаговый метод

Правило 1: Считайте циклы

// Один цикл = O(n)
for (let i = 0; i < n; i++) { }

// Вложенные циклы = O(n²)
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) { }
}

// Три вложенных цикла = O(n³)
for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
        for (let k = 0; k < n; k++) { }
    }
}

Правило 2: Последовательные блоки складываются

// O(n) + O(n) = O(n)
for (let i = 0; i < n; i++) { }  // O(n)
for (let i = 0; i < n; i++) { }  // O(n)
// Итого: O(2n) = O(n)

Правило 3: Отбрасывайте константы

// O(2n) → O(n)
// O(n² + n) → O(n²)
// O(100) → O(1)

Правило 4: Деление пополам = log n

// O(log n)
while (n > 1) {
    n = n / 2;
}

Практические примеры с собеседований

Пример 1: Найти максимум в массиве

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

Пример 2: Проверить уникальность элементов

// Наивное решение — O(n²)
function hasUniqueNaive(array) {
    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {
            if (array[i] === array[j]) return false;
        }
    }
    return true;
}

// Оптимальное решение — O(n)
function hasUniqueOptimal(array) {
    const seen = new Set();
    for (const item of array) {
        if (seen.has(item)) return false;
        seen.add(item);
    }
    return true;
}

Пример 3: Two Sum

// O(n²) — проверяем все пары
function twoSumNaive(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

// O(n) — используем хеш-таблицу
function twoSumOptimal(nums, target) {
    const map = new Map();
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [map.get(complement), i];
        }
        map.set(nums[i], i);
    }
}

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

Big O также используется для оценки памяти:

// O(1) по памяти — используем только переменные
function sum(array) {
    let total = 0;
    for (const num of array) {
        total += num;
    }
    return total;
}

// O(n) по памяти — создаем новый массив
function double(array) {
    const result = [];
    for (const num of array) {
        result.push(num * 2);
    }
    return result;
}

Частые ошибки

Ошибка 1: Забывать о встроенных методах

// Кажется O(n), но на самом деле O(n²)!
function removeDuplicates(array) {
    const result = [];
    for (const item of array) {        // O(n)
        if (!result.includes(item)) {  // includes — O(n)!
            result.push(item);
        }
    }
    return result;
}

// Правильно — O(n)
function removeDuplicatesOptimal(array) {
    return [...new Set(array)];
}

Ошибка 2: Игнорировать сортировку

// sort() в JavaScript — O(n log n)
// Если вызываете sort() внутри цикла — умножайте!

Советы для собеседования

1. Всегда озвучивайте сложность — покажите, что думаете об этом
2. Начните с простого — O(n²) лучше, чем ничего
3. Предложите оптимизацию — "Можно улучшить до O(n) с хеш-таблицей"
4. Упоминайте компромиссы — "Это O(n) по времени, но O(n) по памяти"

Заключение

Big O нотация — это язык, на котором программисты обсуждают эффективность алгоритмов. Освоив его, вы сможете:

• Писать более быстрый код
• Успешно проходить технические собеседования
• Выбирать правильные структуры данных
• Понимать, почему одни решения лучше других

Главное — практика. Решайте задачи и всегда спрашивайте себя: "Какая здесь сложность?"