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

Асимптотическая сложность (Big O нотация)

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

Вместо подсчёта точного количества операций, используется Big O нотация, которая показывает верхний предел роста в worst case сценарии.

Основные классы сложности (от лучших к худшим)

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

// Доступ к элементу массива по индексу
public int getFirstElement(int[] arr) {
    return arr[0]; // Всегда 1 операция, не зависит от размера
}

// Операции в HashMap (в среднем)
Map<String, Integer> map = new HashMap<>();
Integer value = map.get("key"); // O(1) в среднем

// Операции со стеком
Stack<Integer> stack = new Stack<>();
int top = stack.pop(); // O(1)

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

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

// Бинарный поиск в отсортированном массиве
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}
// На массиве из 1,000,000 элементов: ~20 операций (log₂(1,000,000) ≈ 20)

// Поиск в TreeMap/TreeSet
TreeMap<String, Integer> treeMap = new TreeMap<>();
Integer value = treeMap.get("key"); // O(log n)

Характеристика: Размер уменьшается в два раза на каждом шаге.

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

// Линейный поиск
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}
// 100 элементов → ~100 операций в worst case
// 1,000,000 элементов → ~1,000,000 операций

// Перебор списка
for (String item : list) {
    System.out.println(item); // O(n)
}

Характеристика: Операций пропорционально размеру входа.

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

// Сортировка слиянием (Merge Sort)
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);       // T(n/2)
        mergeSort(arr, mid + 1, right);  // T(n/2)
        merge(arr, left, mid, right);     // O(n)
    }
}
// 1,000,000 элементов → ~20,000,000 операций (n * log n)

// Встроенная сортировка (Collections.sort, Arrays.sort)
Collections.sort(list); // O(n log n) в worst case

Характеристика: Комбинация логарифмического и линейного роста.

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

// Сортировка пузырьком (Bubble Sort)
public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {      // n итераций
        for (int j = 0; j < n - i - 1; j++) { // n итераций для каждого i
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}
// 100 элементов → ~10,000 операций
// 1,000 элементов → ~1,000,000 операций (!)

// Вложенные циклы
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // O(1) операция
    }
}

Характеристика: Вложенные циклы, очень быстрый рост.

O(n³) — Кубическая сложность

// Произведение матриц (naive алгоритм)
public static int[][] multiplyMatrices(int[][] A, int[][] B) {
    int n = A.length;
    int[][] C = new int[n][n];
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}
// 100x100 матрицы → 1,000,000 операций
// 1000x1000 матрицы → 1,000,000,000 операций (!)

Характеристика: Три вложенных цикла, непрактично для больших данных.

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

// Рекурсивный расчёт чисел Фибоначчи (неоптимизированный)
public int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// fibonacci(5) → 15 вызовов
// fibonacci(10) → 177 вызовов
// fibonacci(40) → 331,000,000 вызовов (!!)

// Генерация всех подмножеств
for (int mask = 0; mask < (1 << n); mask++) { // 2^n итераций
    // Обработка подмножества
}

Характеристика: Удвоение операций на каждый прирост n. Практически непригодно.

O(n!) — Факториальная сложность

// Генерация всех перестановок (naive)
public void generatePermutations(int[] arr) {
    // Существует n! перестановок
    // 10 элементов → 3,628,800 перестановок
    // 20 элементов → 2,432,902,008,176,640,000 перестановок
}

Характеристика: Самая плохая, используется редко.

Таблица сравнения

Правила для определения Big O

Правило 1: Отбросить константы

// O(3n) → O(n)
// O(2n² + 5n + 10) → O(n²)
for (int i = 0; i < n; i++) {
    doSomething();   // 3 операции
}

Правило 2: Доминирующий термин

// O(n² + n) → O(n²) (n² растёт быстрее)
for (int i = 0; i < n; i++) {        // O(n²)
    for (int j = 0; j < n; j++) {
        count++;
    }
}
for (int i = 0; i < n; i++) {        // O(n)
    count++;
}

Правило 3: Вложенные циклы → умножение

// O(n * m)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        count++;
    }
}

Правило 4: Последовательные циклы → сложение

// O(n + m), часто упрощается до O(n) если m ≈ n
for (int i = 0; i < n; i++) { count++; }  // O(n)
for (int j = 0; j < m; j++) { count++; }  // O(m)

Анализ рекурсии

// Бинарный поиск рекурсивно: O(log n)
private int binarySearchRecursive(int[] arr, int target, int left, int right) {
    if (left > right) return -1;
    int mid = left + (right - left) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
    return binarySearchRecursive(arr, target, left, mid - 1);
}
// Глубина рекурсии: log n
// Операций на уровне: O(1)
// Итого: O(log n)

Временная vs Пространственная сложность

// Временная сложность: O(n)
// Пространственная сложность: O(n)
public List<Integer> sortArray(int[] arr) {
    List<Integer> result = new ArrayList<>(); // O(n) extra space
    for (int num : arr) {                      // O(n) time
        result.add(num);
    }
    return result;
}

// Временная сложность: O(n log n)
// Пространственная сложность: O(1)
public void bubbleSort(int[] arr) {
    // Сортирует на месте (in-place)
    // Только несколько переменных extra space
}

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

• O(1), O(log n) — отлично, даже для 1,000,000 элементов
• O(n), O(n log n) — хорошо, до 10,000,000 элементов
• O(n²) — приемлемо для 10,000 элементов, плохо для 100,000+
• O(2ⁿ) — только для n < 20
• O(n!) — только для n < 10

Асимптотическая сложность — инструмент для сравнения алгоритмов в масштабе, игнорируя константные множители и low-level детали реализации.