> Что такое сложность алгоритмов (Go)

Короткий ответ

Сложность алгоритма показывает, как растёт время работы или потребление памяти при увеличении входных данных. Обычно её выражают в нотации Big O, например O(1), O(log n), O(n), O(n log n), O(n²). Big O описывает верхнюю границу роста и игнорирует константы и младшие члены. Для backend-разработчика это ключевой инструмент оценки масштабируемости кода.

Подход к решению

Сначала определяем, что считаем операцией и какой параметр входа растёт. Затем считаем количество операций как функцию от n. Отбрасываем константы и младшие слагаемые, оставляя доминирующий член. Отдельно оцениваем сложность по времени и по памяти. Для циклов перемножаем вложенность, для последовательных блоков берём максимум. Для рекурсии составляем рекуррентное соотношение или считаем глубину и ветвление.

Пример кода

GO
package main

import "fmt"

// O(n): один проход по слайсу.
func sum(nums []int) int {
	total := 0
	for _, v := range nums {
		total += v
	}
	return total
}

// O(n^2): вложенные циклы по одному и тому же входу.
func hasDuplicateSlow(nums []int) bool {
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			if nums[i] == nums[j] {
				return true
			}
		}
	}
	return false
}

// O(n) по времени, O(n) по памяти: используем map.
func hasDuplicateFast(nums []int) bool {
	seen := make(map[int]struct{}, len(nums))
	for _, v := range nums {
		if _, ok := seen[v]; ok {
			return true
		}
		seen[v] = struct{}{}
	}
	return false
}

func main() {
	fmt.Println(sum([]int{1, 2, 3}))
	fmt.Println(hasDuplicateSlow([]int{1, 2, 3, 2}))
	fmt.Println(hasDuplicateFast([]int{1, 2, 3, 2}))
}

Edge cases

Пустой вход часто даёт O(1) на практике, но асимптотика всё равно оценивается по общему случаю. Худший, средний и лучший случаи могут различаться, например поиск в слайсе. Амортизированная сложность важна для динамических массивов и map в Go. Константы и кэш-локальность могут менять реальную скорость при малых n. Рекурсия добавляет память на стек вызовов.

Как отвечать на собеседовании

Скажите, что Big O описывает рост, а не точное время. Приведите примеры от O(1) до O(n²). Объясните, как считаете сложность циклов и рекурсии. Уточните, что время и память оцениваются отдельно. Покажите пример оптимизации с O(n²) до O(n) через map. Упомяните trade-off между временем и памятью.

Что проверяет интервьюер

Понимание асимптотического анализа и нотации Big O. Умение оценивать код по времени и памяти. Навык видеть узкие места и предлагать оптимизации. Базовое знание структур данных Go и Java. Способность объяснять trade-off простым языком.