Что такое О большое (Big O notation)

Big O — это математическая нотация, описывающая асимптотическую сложность алгоритма. Она показывает, как растёт время выполнения или потребление памяти при увеличении размера входных данных.

Примеры:

• O(1) — константная сложность (доступ к элементу массива)

int getFirstElement(int[] arr) {
    return arr[0];
}

• O(n) — линейная сложность (поиск в неотсортированном массиве)

boolean contains(int[] arr, int target) {
    for (int num : arr) {
        if (num == target) return true;
    }
    return false;
}

• O(n²) — квадратичная сложность (пузырьковая сортировка)

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(arr, j, j+1);
        }
    }
}

Big O описывает худший случай и игнорирует константы (O(2n) → O(n)).