📌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!) — Факториальное время

- Время выполнения пропорционально факториалу размера входных данных.
- Пример: генерация всех перестановок множества.

♻ Сделай репост, чтобы помочь другим.

👉 [club79831840|@Bookflow]