Ответ
Сложность алгоритма — это мера, описывающая зависимость времени выполнения (временная сложность) или объема требуемой памяти (пространственная сложность) от размера входных данных.
Для оценки сложности используется нотация 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
}