7 ключевых сложностей по времени выполнения, которые нужно знать для собеседований по программированию:

1. O(1) — Константное время
- Время выполнения не зависит от размера входных данных.
- 📌 Пример: доступ к элементу массива по индексу.

2. O(log n) — Логарифмическое время
- Время выполнения растёт медленно по мере увеличения входных данных. Обычно встречается в алгоритмах, делящих задачу пополам на каждом шаге.
- 📌Пример: бинарный поиск в отсортированном массиве.

3. O(n) — Линейное время
- Время выполнения растёт пропорционально объёму входных данных.
- 📌Пример: поиск элемента в массиве перебором.

4. O(n log n) — Линеаритмическое время
- Время выполнения немного быстрее, чем квадратичное, и включает логарифмическое количество операций на каждый элемент.
- 📌Пример: сортировка массива алгоритмами быстрой сортировки (quick sort) или слиянием (merge sort).

5. O(n²) — Квадратичное время
- Время выполнения растёт пропорционально квадрату входных данных.
- 📌Пример: сортировка пузырьком, где сравниваются и при необходимости меняются местами все пары элементов.

6. O(2ⁿ) — Экспоненциальное время
- Время выполнения удваивается с каждым новым элементом входа. Такие алгоритмы быстро становятся неэффективными при больших объёмах данных.
- 📌Пример: генерация всех подмножеств множества.

7. O(n!) — Факториальное время
- Время выполнения растёт как факториал от количества входных данных.
- 📌Пример: генерация всех перестановок множества.

👉 Java Portal