Что такое Big O

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

Примеры:

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

int x = array[5]; // O(1)

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

for (int num : array) { // O(n)
    System.out.println(num);
}

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

for (int i = 0; i < n; i++) { // O(n²)
    for (int j = 0; j < n; j++) {
        System.out.println(i + j);
    }
}

Big O помогает сравнивать алгоритмы и выбирать оптимальный для больших данных.