Big O Notation (О-большое)

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

Шпаргалка по алгоритмической сложности

Разберем, как растет время выполнения от самых быстрых алгоритмов к самым ресурсоемким:

• O(1) - Константное время: Время выполнения не меняется при увеличении данных. Пример: Доступ к элементу массива по индексу или вставка в хеш-таблицу.

• O(log n) - Логарифмическое время: Растет логарифмически при увеличении данных. Пример: Бинарный поиск или операции в сбалансированных деревьях.

• O(sqrt(n)) - Корневое время: Растет пропорционально квадратному корню размера данных. Пример: Поиск простых чисел в диапазоне (Решето Эратосфена).

• O(n) - Линейное время: Растет прямо пропорционально объему данных. Пример: Поиск минимума или максимума в неотсортированном массиве.

• O(n log n) - Линеарифмическое время: Комбинация линейного и логарифмического роста. Пример: Эффективные алгоритмы сортировки (Merge Sort, Quick Sort).

• O(n^2) - Квадратичное время: Растет квадратично, часто из-за вложенных циклов. Пример: Простые сортировки (Пузырьком, Выбором).

• O(n^3) - Кубическое время: Растет кубически. Пример: Умножение плотных матриц в лоб.

• O(2^n) - Экспоненциальное время: Время удваивается с каждым новым элементом данных. Пример: Рекурсивное решение задачи коммивояжера.

• O(n!) - Факториальное время: Растет факториально, то есть невероятно быстро. Пример: Задачи на генерацию всех возможных перестановок.

На практике алгоритмы со сложностью от O(1) до O(n log n) считаются эффективными. Если ваш код работает за O(n^2) или хуже - это повод задуматься об оптимизации (исключение составляют случаи, когда объем данных гарантированно мал).

Телеграм: t.me/ainewsline

Источник: vk.com

Комментарии: