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

Алгоритмическая сложность

Алгоритмическая сложность (computational complexity) — это оценка количества ресурсов (время или память), необходимых для выполнения алгоритма в зависимости от размера входных данных. Она помогает оценить эффективность алгоритма и предсказать его поведение при масштабировании.

Два основных типа сложности

Временная сложность — количество операций, выполняемых алгоритмом Пространственная сложность — объём памяти, требуемый для выполнения алгоритма

Нотация Big O (О-большое)

Big O — это математическая нотация для описания верхней границы роста функции. Она игнорирует константы и фокусируется на доминирующем членом.

Основные классы сложности

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

public int getFirstElement(int[] array) {
    return array[0];  // Всегда одна операция
}

1. O(log n) — Логарифмическая сложность (например, двоичный поиск)

public int binarySearch(int[] sortedArray, int target) {
    int left = 0;
    int right = sortedArray.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (sortedArray[mid] == target) {
            return mid;
        } else if (sortedArray[mid] < target) {
            left = mid + 1;  // Исключаем левую половину
        } else {
            right = mid - 1;  // Исключаем правую половину
        }
    }
    return -1;
}

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

public int findMax(int[] array) {
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];  // Проходит через все элементы
        }
    }
    return max;
}

1. O(n log n) — Линейно-логарифмическая сложность (типична для хороших сортировок)

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        mergeSort(array, left, mid);      // O(log n) уровней
        mergeSort(array, mid + 1, right); // O(n) операций на уровне
        merge(array, left, mid, right);
    }
}

private void merge(int[] array, int left, int mid, int right) {
    // O(n) операция слияния
}

1. O(n²) — Квадратичная сложность (вложенные циклы)

public void bubbleSort(int[] array) {
    int n = array.length;
    for (int i = 0; i < n; i++) {           // Внешний цикл: O(n)
        for (int j = 0; j < n - i - 1; j++) { // Внутренний цикл: O(n)
            if (array[j] > array[j + 1]) {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}

1. O(2^n) — Экспоненциальная сложность (рекурсия без оптимизации)

public int fibonacci(int n) {
    if (n <= 1) {
        return n;  // Базовый случай
    }
    // Каждый вызов порождает ещё два вызова
    return fibonacci(n - 1) + fibonacci(n - 2);  // O(2^n) — очень неэффективно
}

1. O(n!) — Факториальная сложность (например, все перестановки)

public void permutations(String str, String result) {
    if (str.length() == 0) {
        System.out.println(result);
        return;
    }
    
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        String remaining = str.substring(0, i) + str.substring(i + 1);
        permutations(remaining, result + c);  // O(n!) — растёт очень быстро
    }
}

Сравнение сложности

Для n = 1000000:

O(1)      → 1 операция
O(log n)  → ~20 операций
O(n)      → 1,000,000 операций
O(n²)     → 1,000,000,000,000 операций ✗ неприемлемо
O(2^n)    → 2^1000000 операций ✗ невозможно

Лучший, средний и худший случаи

public int linearSearch(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

// Лучший случай (Best case): O(1) — элемент в начале
// Средний случай (Average case): O(n) — элемент в середине
// Худший случай (Worst case): O(n) — элемента нет или в конце

Оптимизация сложности

// ❌ Неоптимально: O(n²)
public boolean hasDuplicate(int[] array) {
    for (int i = 0; i < array.length; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if (array[i] == array[j]) {
                return true;
            }
        }
    }
    return false;
}

// ✅ Оптимально: O(n)
public boolean hasDuplicate(int[] array) {
    Set<Integer> seen = new HashSet<>();
    for (int num : array) {
        if (seen.contains(num)) {
            return true;  // Используем O(1) lookup в HashSet
        }
        seen.add(num);
    }
    return false;
}

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

// O(1) пространственная сложность — фиксированное количество памяти
public int sumArray(int[] array) {
    int sum = 0;  // Одна переменная
    for (int num : array) {
        sum += num;
    }
    return sum;
}

// O(n) пространственная сложность — пропорционально входным данным
public List<Integer> duplicateArray(int[] array) {
    List<Integer> result = new ArrayList<>();  // Размер = n
    for (int num : array) {
        result.add(num);
    }
    return result;
}

// O(n) из-за рекурсии — call stack
public int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);  // n вызовов = O(n) памяти
}

Практические советы

1. Анализируй циклы: каждый вложенный цикл умножает сложность
2. Рекурсия: глубина вызовов = пространственная сложность
3. Структуры данных имеют разные сложности операций:
   • Массив: доступ O(1), поиск O(n)
   • HashMap: доступ O(1), поиск O(1)
   • TreeMap: доступ O(log n), поиск O(log n)
   • LinkedList: доступ O(n), поиск O(n)
4. Оптимизируй критические пути — улучшения в часто вызываемых функциях дают больший эффект

Когда это важно

При работе с большими наборами данных (n > 10000) различия становятся критичны:

• O(n log n) vs O(n²): 100,000 элементов = 1.7M vs 10B операций
• выбор правильного алгоритма может ускорить код в 1000+ раз

Алгоритмическая сложность — это один из ключевых навыков, который отличает хороших разработчиков от посредственных.