7 распространённых асимптотических сложностей алгоритмов

1. O(1) — Константное время

- Время выполнения не зависит от размера входных данных.

- Пример: доступ к элементу массива по индексу.

2. O(log n) — Логарифмическое время

- Время выполнения растёт медленно при увеличении размера входных данных. Обычно встречается в алгоритмах, которые на каждом шаге делят задачу пополам.

- Пример: бинарный поиск в отсортированном массиве.

3. O(n) — Линейное время

- Время выполнения растёт прямо пропорционально размеру входных данных.

- Пример: поиск элемента в массиве перебором всех элементов.

4. O(n log n) — Линейно-логарифмическое время

- Время выполнения растёт чуть быстрее линейного, включает логарифмическое число операций для каждого элемента.

- Пример: сортировка массива быстрой сортировкой или сортировкой слиянием.

5. O(n^2) — Квадратичное время

- Время выполнения пропорционально квадрату размера входных данных.

- Пример: сортировка пузырьком, где сравниваются и при необходимости меняются местами все пары элементов.

6. O(2^n) — Экспоненциальное время

- Время выполнения удваивается с каждым новым элементом во входных данных. Такие алгоритмы становятся непрактичными для больших входных размеров.

- Пример: генерация всех подмножеств множества.

7. O(n!) — Факториальное время

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

- Пример: генерация всех перестановок множества.

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

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

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