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

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

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

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

Пример:

// O(n) – линейная сложность  
for (int i = 0; i < n; i++) {  
    System.out.println(i);  
}  

// O(n²) – квадратичная сложность  
for (int i = 0; i < n; i++) {  
    for (int j = 0; j < n; j++) {  
        System.out.println(i + " " + j);  
    }  
}  

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