Что такое асимптотическая нотация и что она обозначает?

Асимптотическая нотация — это способ описания поведения алгоритма при росте размера входных данных. Она показывает, как меняется время выполнения или потребление памяти в зависимости от объёма данных, игнорируя константы и менее значимые слагаемые.

Основные виды асимптотической нотации:

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

Например, алгоритм сортировки с временем O(n²) означает, что при увеличении входных данных вдвое время работы примерно увеличится в 4 раза.