🤔 Что такое BigO notation?

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

🚩Основные концепции Big O notation

🟠Асимптотический анализ:
Big O notation используется для описания асимптотического поведения алгоритмов, то есть их поведения при приближении размера входных данных к бесконечности. Основное внимание уделяется ведущим слагаемым и игнорированию констант и менее значимых слагаемых, поскольку они имеют меньшее влияние на производительность при больших размерах входных данных.

🟠Оценка худшего случая:
Big O notation показывает наихудший возможный сценарий выполнения алгоритма, обеспечивая надежные гарантии его производительности.

🚩Основные классы сложности

🟠O(1) - Константная сложность:
Время выполнения не зависит от размера входных данных. Доступ к элементу массива по индексу.
🟠O(log n) - Логарифмическая сложность:
Время выполнения увеличивается логарифмически с увеличением размера входных данных. Бинарный поиск.
🟠O(n) - Линейная сложность:
Время выполнения растет линейно с увеличением размера входных данных. Линейный поиск.
🟠O(n log n) - Линейно-логарифмическая сложность:
Время выполнения растет линейно с логарифмическим множителем. Быстрая сортировка, сортировка слиянием.
🟠 O(n^2) - Квадратичная сложность:
Время выполнения растет пропорционально квадрату размера входных данных. Сортировка пузырьком, сортировка вставками.
🟠O(2^n) - Экспоненциальная сложность:
Время выполнения удваивается с каждым добавлением нового элемента. Решение задачи о коммивояжере полным перебором.
🟠O(n!) - Факториальная сложность:
Время выполнения растет факториально с увеличением размера входных данных. Полный перебор всех возможных перестановок.

🚩Примеры использования

1⃣Поиск и сортировка:
Анализ эффективности различных алгоритмов сортировки (например, быстрая сортировка vs. сортировка пузырьком).
2⃣Анализ алгоритмов и структур данных:
Оценка времени доступа, вставки и удаления в различных структурах данных (например, массивы, списки, деревья).
3⃣Оптимизация программ:
Помощь в выборе наиболее эффективных алгоритмов и структур данных для решения конкретных задач.

Ставь 👍 и забирай 📚 Базу знаний