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

Она показывает, как быстро растет время выполнения или объем используемой памяти при увеличении размера входа, игнорируя константы и менее значимые слагаемые.

Например:

O(1) — константное время, не зависит от размера данных.
O(n) — время пропорционально размеру входа.
O(n²) — время пропорционально квадрату размера входа.

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

Пример: если у вас есть функция, которая проходит по массиву из n элементов один раз, её сложность O(n). Если внутри цикла есть вложенный цикл по тому же массиву, сложность будет O(n²).

Что такое Big O нотация?