Один и тот же результат можно получить быстрым и медленным способом. На маленьких данных разница незаметна, но на больших медленный алгоритм может работать часами вместо секунд. Чтобы сравнивать алгоритмы независимо от конкретного компьютера, оценивают их сложность — как растёт число операций при росте объёма данных n.
Для этого используют нотацию «О большое» (Big O). Она описывает не точное время, а характер роста, отбрасывая константы и мелочи. Основные классы по возрастанию «тяжести»: • O(1) — постоянная: время не зависит от n (доступ к элементу массива по индексу); • O(log n) — логарифмическая: очень медленный рост (бинарный поиск); • O(n) — линейная: пропорционально n (пройти все элементы); • O(n log n) — «почти линейная»: хорошие сортировки; • O(n²) — квадратичная: вложенные циклы, простые сортировки; • O(2ⁿ) — экспоненциальная: практически неприменима на больших n.
Цель — выбирать алгоритм, который не «взорвётся» при росте данных.