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

Алгоритмическая сложность (O-нотация) описывает, как растёт время выполнения или потребление памяти алгоритма при увеличении размера входных данных.

Основные виды сложности:

• O(1) – константная (доступ по индексу в массиве)
• O(log n) – логарифмическая (бинарный поиск)
• O(n) – линейная (поиск в неотсортированном массиве)
• O(n log n) – линейно-логарифмическая (быстрая сортировка)
• O(n²) – квадратичная (пузырьковая сортировка)

Пример:

// O(n) – линейный поиск
int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Сложность помогает оценить эффективность алгоритма на больших данных.