Что такое сложность алгоритмов? Какие основные классы сложности вы знаете?

Сложность алгоритмов — это мера, описывающая, как количество ресурсов (обычно время выполнения или используемая память) зависит от размера входных данных.

Различают временную сложность (время выполнения) и пространственную сложность (объем памяти).

Основные классы асимптотической сложности (Big O Notation):

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

   arr := [3]int{1, 2, 3}
   _ = arr[0] // O(1)

2. O(log n) – Логарифмическая. Время выполнения растет логарифмически. Характерна для алгоритмов, которые на каждом шаге отбрасывают часть данных. Пример: бинарный поиск в отсортированном массиве.

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

   for _, v := range arr { // O(n)
       // ...
   }

4. O(n log n) – Линейно-логарифмическая. Часто встречается в эффективных алгоритмах сортировки. Пример: быстрая сортировка (Quick Sort), сортировка слиянием (Merge Sort).

5. O(n²) – Квадратичная. Время выполнения растет пропорционально квадрату размера данных. Типично для вложенных циклов. Пример: пузырьковая сортировка (Bubble Sort).

   for i := 0; i < n; i++ { // O(n²)
       for j := 0; j < n; j++ {
           // ...
       }
   }

6. O(2ⁿ) – Экспоненциальная. Время выполнения удваивается с каждым новым элементом. Такие алгоритмы очень медленные. Пример: рекурсивный расчет чисел Фибоначчи без мемоизации.

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