7 распространённых асимптотических сложностей алгоритмов
1. O(1) — Константное время
- Время выполнения не зависит от размера входных данных.
- Пример: доступ к элементу массива по индексу.
2. O(log n) — Логарифмическое время
- Время выполнения растёт медленно при увеличении размера входных данных. Обычно встречается в алгоритмах, которые на каждом шаге делят задачу пополам.
- Пример: бинарный поиск в отсортированном массиве.
3. O ( n ) — Линейное время
- Время выполнения растёт прямо пропорционально размеру входных данных.
- Пример: поиск элемента в массиве перебором всех элементов.
4. O(n log n) — Линейно-логарифмическое время
- Время выполнения растёт чуть быстрее линейного, включает логарифмическое число операций для каждого элемента.
- Пример: сортировка массива быстрой сортировкой или сортировкой слиянием.
5. O(n²) — Квадратичное время
- Время выполнения пропорционально квадрату размера входных данных.
- Пример: сортировка пузырьком, где сравниваются и при необходимости меняются местами все пары элементов.
6. O(2ⁿ) — Экспоненциальное время
- Время выполнения удваивается с каждым новым элементом во входных данных. Такие алгоритмы становятся непрактичными для больших входных размеров.
- Пример: генерация всех подмножеств множества.
7. O(n!) — Факториальное время
- Время выполнения пропорционально факториалу размера входных данных.
- Пример: генерация всех перестановок множества.
1. O(1) — Константное время
- Время выполнения не зависит от размера входных данных.
- Пример: доступ к элементу массива по индексу.
2. O(log n) — Логарифмическое время
- Время выполнения растёт медленно при увеличении размера входных данных. Обычно встречается в алгоритмах, которые на каждом шаге делят задачу пополам.
- Пример: бинарный поиск в отсортированном массиве.
3. O ( n ) — Линейное время
- Время выполнения растёт прямо пропорционально размеру входных данных.
- Пример: поиск элемента в массиве перебором всех элементов.
4. O(n log n) — Линейно-логарифмическое время
- Время выполнения растёт чуть быстрее линейного, включает логарифмическое число операций для каждого элемента.
- Пример: сортировка массива быстрой сортировкой или сортировкой слиянием.
5. O(n²) — Квадратичное время
- Время выполнения пропорционально квадрату размера входных данных.
- Пример: сортировка пузырьком, где сравниваются и при необходимости меняются местами все пары элементов.
6. O(2ⁿ) — Экспоненциальное время
- Время выполнения удваивается с каждым новым элементом во входных данных. Такие алгоритмы становятся непрактичными для больших входных размеров.
- Пример: генерация всех подмножеств множества.
7. O(n!) — Факториальное время
- Время выполнения пропорционально факториалу размера входных данных.
- Пример: генерация всех перестановок множества.