7 обязательных сложностей алгоритмов (Big-O) для собеседований:

1. 𝐎(1) — 𝐤𝐨𝐧𝐬𝐭𝐚𝐧𝐭𝐧𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

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

2. 𝐎(𝐥𝐨𝐠 𝐧) — 𝐥𝐨𝐠𝐚𝐫𝐢𝐟𝐦𝐢𝐜𝐡𝐞𝐬𝐤𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

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

3. 𝐎(𝐧) — 𝐥𝐢𝐧𝐞𝐲𝐧𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

- Время растёт линейно относительно размера входных данных.
- Пример: поиск элемента в массиве перебором.

4. 𝐎(𝐧 𝐥𝐨𝐠 𝐧) — 𝐥𝐢𝐧𝐞𝐲𝐧𝐨-𝐥𝐨𝐠𝐚𝐫𝐢𝐟𝐦𝐢𝐜𝐡𝐞𝐬𝐤𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

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

5. 𝐎(𝐧^2) — 𝐤𝐯𝐚𝐝𝐫𝐚𝐭𝐢𝐜𝐡𝐞𝐬𝐤𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

- Время растёт пропорционально квадрату входа.
-Пример: bubble sort, где происходит сравнение и возможный swap каждой пары элементов.

6. 𝐎(2^𝐧) — 𝐞𝐤𝐬𝐩𝐨𝐧𝐞𝐧𝐭𝐬𝐢𝐚𝐥𝐧𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

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

7. 𝐎(𝐧!) — 𝐟𝐚𝐤𝐭𝐨𝐫𝐢𝐚𝐥𝐧𝐚𝐲𝐚 𝐬𝐥𝐨𝐳𝐡𝐧𝐨𝐬𝐭𝐢

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

👉 @PythonPortal