Сегодня разбираем одну из самых важных тем для любого инженера и разработчика - 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) или хуже - это повод задуматься об оптимизации (исключение составляют случаи, когда объем данных гарантированно мал).
Шпаргалка по алгоритмической сложности
Разберем, как растет время выполнения от самых быстрых алгоритмов к самым ресурсоемким:
• 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) или хуже - это повод задуматься об оптимизации (исключение составляют случаи, когда объем данных гарантированно мал).
