Ответ
Сложность алгоритмов — это мера, описывающая, как количество ресурсов (обычно время выполнения или используемая память) зависит от размера входных данных.
Различают временную сложность (время выполнения) и пространственную сложность (объем памяти).
Основные классы асимптотической сложности (Big O Notation):
-
O(1) – Константная. Время выполнения не зависит от размера данных. Пример: доступ к элементу массива по индексу.
arr := [3]int{1, 2, 3} _ = arr[0] // O(1) -
O(log n) – Логарифмическая. Время выполнения растет логарифмически. Характерна для алгоритмов, которые на каждом шаге отбрасывают часть данных. Пример: бинарный поиск в отсортированном массиве.
-
O(n) – Линейная. Время выполнения растет прямо пропорционально размеру данных. Пример: перебор всех элементов в срезе.
for _, v := range arr { // O(n) // ... } -
O(n log n) – Линейно-логарифмическая. Часто встречается в эффективных алгоритмах сортировки. Пример: быстрая сортировка (Quick Sort), сортировка слиянием (Merge Sort).
-
O(n²) – Квадратичная. Время выполнения растет пропорционально квадрату размера данных. Типично для вложенных циклов. Пример: пузырьковая сортировка (Bubble Sort).
for i := 0; i < n; i++ { // O(n²) for j := 0; j < n; j++ { // ... } } -
O(2ⁿ) – Экспоненциальная. Время выполнения удваивается с каждым новым элементом. Такие алгоритмы очень медленные. Пример: рекурсивный расчет чисел Фибоначчи без мемоизации.
-
O(n!) – Факториальная. Время выполнения растет факториально. Применяется к очень небольшим наборам данных. Пример: решение задачи коммивояжёра методом полного перебора.
Ответ 18+ 🔞
Так, слушай сюда, про сложность алгоритмов, это ж, блядь, как мерить, насколько твой код будет тормозить, когда данных станет овердохуища.
Вот смотри, есть два главных замера: временная сложность (сколько секунд твоя поделка будет думать) и пространственная (сколько оперативки сожрёт, пока думает). И измеряют это всё через Big O нотацию, это типа как универсальный язык для оценки тормознутости.
Основные градации, от быстрых до ебейших:
-
O(1) – Константная. Вообще похуй на размер данных. Время одно и то же. Пример: достать пиво из холодильника по известной полке.
arr := [3]int{1, 2, 3} _ = arr[0] // O(1) - взял и выпил. -
O(log n) – Логарифмическая. Растёт медленно, как твоя зарплата. На каждом шаге отбрасывает половину проблем. Пример: найти нужную песню в плейлисте, отсортированном по алфавиту, методом "деления пополам".
-
O(n) – Линейная. Чем больше данных, тем дольше. Прямая зависимость, всё честно. Пример: пересчитать всю сдачу в кошельке по одной монетке.
for _, v := range arr { // O(n) - считаю каждую копейку. // ... } -
O(n log n) – Линейно-логарифмическая. Быстрее, чем квадрат, но медленнее, чем просто линия. Царица сортировок тут обитает. Пример: быстрая сортировка (Quick Sort) – умный способ разложить бардак в стопке бумаг.
-
O(n²) – Квадратичная. Вот тут начинается пиздец. Два вложенных цикла – и привет, на больших данных ждём, как второго пришествия. Пример: пузырьковая сортировка – тупой перебор, как сравнивать каждого гостя на вечеринке с каждым, чтобы понять, кто выше.
for i := 0; i < n; i++ { // O(n²) - ебать, сейчас мозг сломается. for j := 0; j < n; j++ { // ... } } -
O(2ⁿ) – Экспоненциальная. А это уже чистое безумие. С каждым новым элементом время работы хуярит вверх, как сумасшедшее. Для реальных задач – полный ахтунг. Пример: рекурсивный расчёт чисел Фибоначчи без оптимизации – считаешь одно и то же столько раз, что волосы дыбом.
-
O(n!) – Факториальная. Абсолютный пиздец, апогей тормозов. Только для игрушечных данных, и то страшно. Пример: задача коммивояжёра полным перебором – перебрать все возможные маршруты. Для 10 городов уже нихуя не вариант.
Короче, суть в чём: если видишь в своём коде вложенные циклы по тем же данным – бля, подозрение ебать чувствую, это скорее всего O(n²) и тебе пизда. Ищи способ сделать через хэш-таблицу (словарь) или сортировку. Всем чмоки в этом чятике.