Что такое асимптотический анализ?

Асимптотический анализ

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

Вместо подсчета точного количества операций (которое зависит от конкретной машины), мы определяем порядок роста времени выполнения.

Нотация Big-O (O)

Big-O описывает верхнюю границу сложности — наихудший сценарий.

// O(1) — Constant time
public int getFirstElement(int[] arr) {
    return arr[0]; // Одна операция, независимо от размера
}

// O(n) — Linear time
public int sum(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        total += arr[i]; // n итераций
    }
    return total;
}

// O(n²) — Quadratic time
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - 1; j++) { // Вложенные циклы
            if (arr[j] > arr[j + 1]) {
                // swap
            }
        }
    }
}

// O(log n) — Logarithmic time
public int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2; // Каждая итерация уменьшает область поиска на половину
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// O(n log n) — Linearithmic time
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);      // T(n/2)
        mergeSort(arr, mid + 1, right); // T(n/2)
        merge(arr, left, mid, right);   // O(n)
    }
}

Общие классы сложности (в порядке роста)

Другие нотации

Omega (Ω) — Нижняя граница

// Линейный поиск
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}
// Лучший случай: O(1) — элемент в начале массива
// Худший случай: O(n) — элемента нет
// Ω(1) — в лучшем случае

Theta (Θ) — Точная граница

// Если алгоритм ВСЕГДА выполняется за O(n) — это Θ(n)
public void printAll(int[] arr) {
    for (int x : arr) {
        System.out.println(x); // n итераций всегда
    }
}
// Θ(n)

Правила анализа

1. Постоянные множители игнорируются

// O(2n) = O(n)
// O(5n) = O(n)
for (int i = 0; i < n; i++) { ... }  // n итераций
for (int i = 0; i < n; i++) { ... }  // n итераций

2. Младшие члены игнорируются

// O(n² + n) = O(n²)
// Доминирует n²
for (int i = 0; i < n; i++) {        // O(n²)
    for (int j = 0; j < n; j++) { }
}
for (int i = 0; i < n; i++) { }     // O(n) — игнорируется

3. Последовательные операции складываются

// O(n) + O(n) = O(2n) = O(n)
for (int i = 0; i < n; i++) { }     // O(n)
for (int i = 0; i < n; i++) { }     // O(n)

4. Вложенные циклы умножаются

// O(n) * O(n) = O(n²)
for (int i = 0; i < n; i++) {       // O(n)
    for (int j = 0; j < n; j++) {   // O(n)
        // операция
    }
}

Практические примеры

Анализ алгоритма поиска подстроки (Naive)

public int findSubstring(String text, String pattern) {
    for (int i = 0; i < text.length(); i++) {           // O(n)
        for (int j = 0; j < pattern.length(); j++) {    // O(m)
            if (text.charAt(i + j) != pattern.charAt(j)) {
                break;
            }
        }
    }
    return -1;
}
// Временная сложность: O(n * m), где n — длина текста, m — длина шаблона

Анализ алгоритма сортировки

// Bubble Sort
public void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {              // n
        for (int j = 0; j < arr.length - 1 - i; j++) {  // n-1, n-2, ..., 1
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}
// T(n) = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n²)

// Merge Sort
public void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);      // T(n/2)
        mergeSort(arr, mid + 1, right); // T(n/2)
        merge(arr, left, mid, right);   // O(n)
    }
}
// T(n) = 2*T(n/2) + O(n) = O(n log n)

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

// O(1) — Constant space
public int sum(int[] arr) {
    int total = 0; // одна переменная
    for (int x : arr) total += x;
    return total;
}

// O(n) — Linear space
public List<Integer> getDoubles(int[] arr) {
    List<Integer> result = new ArrayList<>(); // n элементов
    for (int x : arr) result.add(x * 2);
    return result;
}

// O(log n) — Logarithmic space (рекурсия)
public int binarySearch(int[] arr, int target, int left, int right) {
    // Call stack: O(log n)
    if (left > right) return -1;
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target) return binarySearch(arr, target, mid + 1, right);
    return binarySearch(arr, target, left, mid - 1);
}

Как выбрать алгоритм

// Для n = 1000 элементов:
O(1)       → 1 операция
O(log n)   → 10 операций
O(n)       → 1000 операций
O(n log n) → 10000 операций
O(n²)      → 1000000 операций
O(2^n)     → 2^1000 операций (невозможно!)

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