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

Расчет сложности алгоритма (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);  
    }  
}  

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