Нотация Big O описывает, как увеличивается время выполнения алгоритма или объём используемой памяти в зависимости от размера входных данных. Она ориентируется на худший случай и не учитывает константы и члены низшего порядка.
Распространённые сложности (от самой быстрой к самой медленной):
O(1) — Константная: время не зависит от размера входных данных
O(log n) — Логарифмическая: делит задачу пополам на каждом шаге (бинарный поиск)
O(n) — Линейная: обрабатывает каждый элемент один раз
O(n log n) — Линейно-логарифмическая: эффективная сортировка (Merge Sort, Quick Sort)
O(n²) — Квадратичная: вложенные циклы (Bubble Sort, полный перебор)
O(2^n) — Экспоненциальная: количество операций удваивается с каждым новым элементом
O(n!) — Факториальная: все возможные перестановки
Почему это важно:
При n = 1 000: O(n) = 1 000 операций, O(n²) = 1 000 000 операций
Выбор правильного алгоритма может сократить время вычислений с нескольких часов до нескольких секунд.
Правила Big O:
1. Убирайте константы: O(2n) → O(n)
2. Убирайте члены низшего порядка: O(n² + n) → O(n²)
3. Учитывайте доминирующий член при больших значениях n
Похожие алгоритмы
Частые вопросы
- Что такое Нотация Big O?
- Нотация Big O описывает, как увеличивается время выполнения алгоритма или объём используемой памяти в зависимости от размера входных данных. Она ориентируется на худший случай и не учитывает константы и члены низшего порядка.
- Какова сложность Нотация Big O?
- Нотация Big O объясняется с помощью пошаговой визуализации, включая временную и пространственную сложность.
- Для кого предназначена визуализация Нотация Big O?
- Визуализация Нотация Big O рассчитана на начальный уровень в категории «Основы». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Нотация Big O?
- В той же категории (Основы) вы можете изучить: Recursion, Two Pointers, Sliding Window. Каждый из них имеет интерактивную визуализацию.