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

# Временная сложность алгоритма (Time Complexity)

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

Big O нотация

Big O описывает worst-case сценарий — максимальное количество операций при самом неудачном раскладе.

O(1)      < O(log n)    < O(n)      < O(n log n)   < O(n²)     < O(n³)     < O(2^n)
Постоянная Логарифм   Линейная  Линейно-лог  Квадратная Кубическая Экспоненциальная

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

O(1) - Постоянная сложность

Время не зависит от размера входных данных.

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

// O(1)
public int getFromHashMap(Map<String, Integer> map, String key) {
    return map.get(key);  // Константное время
}

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

Время растёт логарифмически. Каждый шаг исключает половину данных.

// O(log n) - Binary Search
public int binarySearch(int[] sortedArr, int target) {
    int left = 0, right = sortedArr.length - 1;
    
    while (left <= right) {
        int mid = (left + right) / 2;
        if (sortedArr[mid] == target) {
            return mid;
        } else if (sortedArr[mid] < target) {
            left = mid + 1;  // Исключаем левую половину
        } else {
            right = mid - 1; // Исключаем правую половину
        }
    }
    return -1;
}
// Массив из 1000000 элементов: ~20 итераций

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

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

// O(n) - Linear Search
public int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

// O(n) - Summing array
public int sumArray(int[] arr) {
    int sum = 0;
    for (int num : arr) {
        sum += num;  // n операций
    }
    return sum;
}

O(n log 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);        // Разделяем (log n)
        mergeSort(arr, mid + 1, right);   // Разделяем (log n)
        merge(arr, left, mid, right);     // Сливаем (n)
    }
}

// O(n log n) - Quick Sort (среднее)
public void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);      // log n уровней
        quickSort(arr, pi + 1, high);     // n операций на уровень
    }
}

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

Вложенные циклы. Часто говорит о неоптимальном решении.

// O(n²) - Bubble Sort
public void bubbleSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n; i++) {           // n итераций
        for (int j = 0; j < n - i - 1; j++) { // n итераций
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
            }
        }
    }
}

// O(n²) - Nested loops
public void findPairs(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            System.out.println(arr[i] + ", " + arr[j]);
        }
    }
}

O(2^n) - Экспоненциальная сложность

Невероятно медленно растёт. Обычно неприемлемо для больших n.

// O(2^n) - Naive Fibonacci
public int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
    // Для n=40: ~1 млрд операций!
}

// O(n) - Optimized Fibonacci (с memoization)
public int fibonacciOptimized(int n, Map<Integer, Integer> memo) {
    if (n <= 1) return n;
    if (memo.containsKey(n)) return memo.get(n);
    
    int result = fibonacciOptimized(n - 1, memo) + 
                 fibonacciOptimized(n - 2, memo);
    memo.put(n, result);
    return result;
}

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

Чаще всего при переборе всех перестановок.

// O(n!) - Generate all permutations
public void permute(String str, int l, int r) {
    if (l == r) {
        System.out.println(str);
    } else {
        for (int i = l; i <= r; i++) {
            str = swap(str, l, i);
            permute(str, l + 1, r);
            str = swap(str, l, i);
        }
    }
}

Сложность типичных операций

Операция           Сложность
─────────────────────────────
Array access       O(1)
Array search       O(n)
Array insert       O(n)
Array delete       O(n)
HashMap get        O(1)
HashMap insert     O(1)
HashMap delete     O(1)
LinkedList access  O(n)
LinkedList insert  O(1)
LinkedList delete  O(1)
Binary Search      O(log n)
Merge Sort         O(n log n)
Quick Sort         O(n²) worst, O(n log n) avg

Анализ примера: Two Sum

// Решение 1: Brute Force O(n²)
public int[] twoSum_BruteForce(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[] {i, j};
            }
        }
    }
    return null;
}

// Решение 2: HashMap O(n)
public int[] twoSum_HashMap(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[] {map.get(complement), i};
        }
        map.put(nums[i], i);  // O(1) операция
    }
    return null;
}
// Для массива из 10000 элементов:
// Brute Force: ~50 млн операций
// HashMap:     ~10000 операций

Как анализировать сложность

1. Посчитай циклы

   • 1 цикл = O(n)
   • 2 вложенных цикла = O(n²)
   • цикл делит пополам = O(log n)

2. Отброси константы

   • O(2n) = O(n)
   • O(n + 100) = O(n)

3. Оставь доминирующий член

   • O(n² + n) = O(n²)
   • O(n log n + n) = O(n log n)

4. Проверь пространственную сложность

   • HashMap: O(n) дополнительная память
   • Сортировка на месте: O(1) дополнительная память

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

// При выборе между решениями:
if (n < 1000) {
    // O(n²) приемлемо
} else if (n < 1000000) {
    // Нужна O(n log n) или лучше
} else {
    // Только O(n) или O(log n)
}

Понимание временной сложности критично для написания масштабируемого и эффективного кода.