Что такое Big O?

Big O: анализ асимптотической сложности

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

Drug словами, Big O отвечает на вопрос: "Во сколько раз медленнее/больше памяти потребует алгоритм, если входные данные увеличатся в 10, 100 или 1000 раз?"

Основная идея

Big O анализирует худший сценарий и игнорирует константные множители:

// O(n) - линейный
public void printArray(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]); // Повторится n раз
    }
}

// O(n^2) - квадратичный
public void printPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + " " + arr[j]);
        }
    }
}

// O(1) - постоянный
public int getFirstElement(int[] arr) {
    return arr[0]; // Один доступ независимо от размера массива
}

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

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

Операция выполняется за одно и то же время независимо от размера данных:

// Доступ к элементу по индексу в массиве
int element = arr[5];

// Вставка в HashMap
map.put("key", "value");

// Получение из HashMap
String value = map.get("key");

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;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // Максимум log2(n) итераций
}

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

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

// Поиск элемента в неотсортированном массиве
public boolean contains(int[] arr, int target) {
    for (int num : arr) { // n итераций в худшем случае
        if (num == target) return true;
    }
    return false;
}

// Сумма элементов массива
public int sum(int[] arr) {
    int total = 0;
    for (int num : arr) { // n итераций
        total += num;
    }
    return total;
}

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

Типично для эффективных алгоритмов сортировки (Merge Sort, Quick Sort):

// Merge Sort
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);        // Разделение
        mergeSort(arr, mid + 1, right);   // Разделение
        merge(arr, left, mid, right);     // Слияние O(n)
    }
    // Всего: O(n log n)
}

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 итераций
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// Проверка всех пар элементов
public boolean hasDuplicate(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) { // Вложенные циклы
            if (arr[i] == arr[j]) return true;
        }
    }
    return false;
}

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

Три вложенных цикла:

// Наивное умножение матриц
public int[][] multiplyMatrices(int[][] a, int[][] b, int n) {
    int[][] c = new int[n][n];
    for (int i = 0; i < n; i++) {        // n итераций
        for (int j = 0; j < n; j++) {    // n итераций
            for (int k = 0; k < n; k++) { // n итераций
                c[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return c;
}

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

Время удваивается при каждом добавлении элемента к входу:

// Генерация всех подмножеств (power set)
public List<List<Integer>> powerSet(int[] arr) {
    List<List<Integer>> result = new ArrayList<>();
    int totalSubsets = 1 << arr.length; // 2^n
    
    for (int i = 0; i < totalSubsets; i++) {
        List<Integer> subset = new ArrayList<>();
        for (int j = 0; j < arr.length; j++) {
            if ((i & (1 << j)) != 0) {
                subset.add(arr[j]);
            }
        }
        result.add(subset);
    }
    return result;
}

// Рекурсивное решение проблемы коммивояжёра
public int tsp(int[][] dist, int visited, int pos) {
    if (visited == (1 << dist.length) - 1) {
        return dist[pos][0];
    }
    
    int ans = Integer.MAX_VALUE;
    for (int city = 0; city < dist.length; city++) {
        if ((visited & (1 << city)) == 0) {
            ans = Math.min(ans, dist[pos][city] + tsp(dist, visited | (1 << city), city));
        }
    }
    return ans;
}

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

Худший вариант. Нужно перебрать все перестановки:

// Все перестановки строки
public List<String> permute(String str) {
    List<String> result = new ArrayList<>();
    permute(str.toCharArray(), 0, str.length() - 1, result);
    return result; // n! перестановок
}

private void permute(char[] arr, int l, int r, List<String> result) {
    if (l == r) {
        result.add(new String(arr));
    } else {
        for (int i = l; i <= r; i++) {
            swap(arr, l, i);
            permute(arr, l + 1, r, result);
            swap(arr, l, i);
        }
    }
}

Пример анализа реального алгоритма

public int countOperations(int[] arr) {
    int count = 0;
    
    // O(1)
    int first = arr[0];
    
    // O(n)
    for (int i = 0; i < arr.length; i++) {
        System.out.println(i);
    }
    
    // O(n^2)
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + arr[j]);
        }
    }
    
    // O(log n)
    int x = 1;
    while (x < arr.length) {
        System.out.println(x);
        x *= 2;
    }
    
    // Итого: O(1) + O(n) + O(n^2) + O(log n) = O(n^2)
}

Почему Big O важна?

1. Масштабируемость — O(n) алгоритм работает с 1 млн элементов, O(n²) — едва ли с 10 тыс
2. Выбор структур данных — HashMap O(1) лучше List O(n) для поиска
3. Оптимизация — понимание сложности помогает улучшать производительность
4. Интервью — собеседующие всегда спрашивают о Big O

Шпаргалка

Понимание Big O — это фундамент компьютерных наук и обязательный навык для любого разработчика.