7 ключевых сложностей времени исполнения

1. O(1) — Постоянная сложность

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

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

2. O(log n) — Логарифмическая сложность

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

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

3. O(n) — Линейная сложность

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

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

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

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

- Пример: Алгоритмы сортировки, такие как быстрая сортировка (quicksort) или сортировка слиянием (mergesort).

5. O(n^2) — Квадратичная сложность

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

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

6. O(2*x) — Экспоненциальная сложность

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

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

7. O(n! ) — Факториальная сложность

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

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

Телеграм: t.me/ainewsline

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

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