Parlez-moi de la notation asymptotique Big O : qu'est-ce que c'est, quels types existent et à quoi servent-ils

Асимптотическая нотация Big O — это способ описания оценки времени выполнения или потребления памяти алгоритма в зависимости от размера входных данных.

Основные виды:

• O(1) — константное время: выполнение не зависит от размера входа.
• O(log n) — логарифмическое время: например, бинарный поиск.
• O(n) — линейное время: перебор всех элементов.
• O(n log n) — часто встречается в эффективных алгоритмах сортировки.
• O(n²) — квадратичное время: вложенные циклы по всему массиву.

Используется для сравнения эффективности алгоритмов и оценки масштабируемости. Например, если алгоритм с O(n) работает быстро на 1000 элементах, то при увеличении до миллиона элементов время увеличится примерно в 1000 раз.

Big O помогает понять, как алгоритм поведёт себя при росте данных, и выбрать оптимальный подход.