Ответ
Сложность алгоритма — это мера, описывающая зависимость времени выполнения (временная сложность) или объема требуемой памяти (пространственная сложность) от размера входных данных.
Для оценки сложности используется нотация Big-O (O-большое), которая описывает поведение алгоритма в худшем случае при увеличении объема данных.
Основные классы сложности:
O(1)— Константная: время выполнения не зависит от размера данных (например, доступ к элементу массива по индексу).O(log n)— Логарифмическая: время выполнения растет логарифмически (например, бинарный поиск в отсортированном массиве).O(n)— Линейная: время выполнения растет прямо пропорционально размеру данных (например, перебор всех элементов массива).O(n log n)— Линейно-логарифмическая: типична для эффективных алгоритмов сортировки (например, быстрая сортировка, сортировка слиянием).O(n²)— Квадратичная: время выполнения растет пропорционально квадрату размера данных (например, вложенные циклы, сортировка пузырьком).O(2ⁿ)— Экспоненциальная: очень медленные алгоритмы, часто связанные с полным перебором (например, рекурсивный расчет чисел Фибоначчи).
Примеры на Go:
// O(n) — Линейная сложность
// Время работы зависит от количества элементов в срезе.
func findElement(slice []int, element int) bool {
for _, v := range slice { // Цикл выполнится n раз
if v == element {
return true
}
}
return false
}
// O(n²) — Квадратичная сложность
// Вложенный цикл приводит к n*n итерациям.
func hasDuplicates(slice []int) bool {
n := len(slice)
for i := 0; i < n; i++ { // Выполняется n раз
for j := 0; j < n; j++ { // Выполняется n раз для каждой итерации внешнего цикла
if i != j && slice[i] == slice[j] {
return true
}
}
}
return false
}Ответ 18+ 🔞
Давай разберёмся с этой вашей сложностью алгоритмов, а то народ путается, как мудаки в тёмной бане.
Сложность — это, грубо говоря, мера того, насколько твой алгоритм начинает тупить и жрать память, когда данных становится овердохуища. Есть два главных вида: временная (сколько времени жрёт) и пространственная (сколько памяти хавает).
Чтобы это всё не на пальцах объяснять, умные дядьки придумали нотацию Big-O (О-большое). Она показывает, как алгоритм себя ведёт в самом пиздецовом случае, когда данных навалило, как говна за баней.
Основные градации этой вашей сложности:
O(1)— Константная. Вообще похуй на размер данных. Время одно и то же. Как взять бутылку из холодильника — открыл дверцу, взял. Неважно, полный холодильник или пустой.O(log n)— Логарифмическая. Растёт медленно, как зарплата. Типичный пример — бинарный поиск. Ты каждый раз отбрасываешь половину хуйни и ищешь в оставшейся.O(n)— Линейная. Время растёт прямо пропорционально данным. Если элементов в 10 раз больше, и работать будешь в 10 раз дольше. Как пересчитать всех овец в загоне.O(n log n)— Линейно-логарифмическая. Золотая середина для сортировок. Быстрая сортировка (quicksort) и сортировка слиянием (merge sort) — вот их поштамп.O(n²)— Квадратичная. Вот тут начинается пиздец. Время растёт как квадрат размера данных. Два вложенных цикла — и привет. Сортировка пузырьком — её любимый пример, алгоритм для мазохистов.O(2ⁿ)— Экспоненциальная. А это уже полный ахтунг, ёперный театр. Время выстреливает в космос. Рекурсивный расчёт чисел Фибоначчи без оптимизации — смотри, как твой комп задымится.
Ну и примерчики на Go, чтобы не быть голословным:
// O(n) — Линейная. Прошлись по всему срезу один раз.
func findElement(slice []int, element int) bool {
for _, v := range slice { // Цикл на n итераций
if v == element {
return true
}
}
return false
}
// O(n²) — Квадратичная. Два цикла, один в другом — классика жанра.
func hasDuplicates(slice []int) bool {
n := len(slice)
for i := 0; i < n; i++ { // n раз
for j := 0; j < n; j++ { // и каждый раз ещё n раз... n*n, ёбта!
if i != j && slice[i] == slice[j] {
return true
}
}
}
return false
}Короче, суть в чём: прежде чем писать код, подумай, не получится ли у тебя квадратичная или, не дай бог, экспоненциальная сложность. А то запустишь на продакшене — и волнение ебать, сервак накрылся медным тазом.