Что такое O(n)

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

// O(n) — линейный: время растёт прямо пропорционально размеру данных
for (int x : array) {
    System.out.println(x);
}

// O(1) — константный: время не зависит от размера данных
int first = array[0];

Если массив вырос в 10 раз, O(n)-алгоритм будет работать примерно в 10 раз дольше, а O(1) — как и раньше, мгновенно.

Копнуть глубже

Главные классы сложности, от лучшего к худшему:

Обозначение	Название	Пример
`O(1)`	константа	`map.get(key)`, `array[i]`
`O(log n)`	логарифм	бинарный поиск
`O(n)`	линейная	перебор массива
`O(n log n)`	линеаризм	хорошая сортировка (`Collections.sort`)
`O(n²)`	квадратичная	вложенный цикл по тому же массиву

Big-O — это про худший случай и про большие n. Для маленьких данных разница между O(n) и O(n²) незаметна, но на миллионах записей O(n²)-алгоритм может работать часами там, где O(n log n) справится за секунды.

🎤 Закрыл тему, если можешь объяснить:

• что показывает Big-O и почему это не секунды, а порядок роста;
• назвать порядок основных классов сложности от лучшего к худшему (если дошёл до 2-го слоя).