Сложность алгоритмов и Big O

Сложность — это не «сколько миллисекунд на моём ноутбуке».

Это ответ на другой вопрос: что будет, если вход станет в десять раз больше? Время вырастет в десять раз? В сто? Почти не изменится?

Буква O в Big O — верхняя оценка. Говорим: рост не быстрее, чем функция f. Константы и мелкие слагаемые отбрасывают. O(2n) и O(n) — один класс: линейный.

Пример. Список из 10 заказов: один проход и два прохода оба мгновенны. Список из миллиона: один проход ещё терпим, вложенный цикл по каждой паре — уже минуты.

На бэкенде «вход n» — это часто число строк в таблице, длина слайса, число RPC. N+1 запросов к базе — это O(n) походов по сети, даже если каждый SQL сам по себе дешёвый. Полный проход таблицы — O(n) чтений с диска. Лишний индекс ускоряет чтение и добавляет работу на каждую запись.

Что означает O(f)

Фраза «поиск в отсортированном массиве — O(log n)» говорит о числе шагов, не о наносекундах. Нужна модель: сколько раз посмотрели элемент, сколько раз сходили в базу, сколько раз скопировали буфер.

Без модели «это O(1)» звучит пусто. Поиск в хэш-таблице в среднем константный. Тот же lookup в холодный Redis через сеть — это round-trip, цена сети, не цена хэша.

Пример. Телефонная книга на миллион имён. Идти с первой страницы — около миллиона шагов, O(n). Открыть середину, отбросить половину, снова середину — около 20 шагов. Это O(log n). Так работает бинарный поиск. Так же устроена высота B-tree.

Есть и нижняя граница. Если сортировка только сравнивает элементы, в худшем случае она не быстрее O(n log n). Дерево решений не может быть ниже логарифма от n!. Counting sort и radix sort на целых с узким диапазоном — другая модель: они не «ломают» эту границу, они не сравнивают.

func maxPairSum(a []int) int { // O(n)
	if len(a) == 0 {
		return 0
	}
	m1, m2 := a[0], a[0]
	for _, v := range a {
		if v > m1 {
			m2, m1 = m1, v
		} else if v > m2 {
			m2 = v
		}
	}
	return m1 + m2
}

func naivePairs(a []int) int { // O(n²)
	best := 0
	for i := range a {
		for j := range a {
			if i != j && a[i]+a[j] > best {
				best = a[i] + a[j]
			}
		}
	}
	return best
}

Средний и худший случай

Quicksort в среднем O(n log n). В худшем — O(n²): пивот всегда крайний, данные почти отсортированы. Хэш-таблица в среднем O(1) на поиск. В худшем — O(n): все ключи свалились в одну корзину.

Амортизация — когда редкая дорогая операция размазывается по многим дешёвым. append у слайса в типичном случае O(1) амортизированно. Пока хватает ёмкости, это запись в массив. Когда не хватает, рантайм выделяет новый массив побольше и копирует элементы. Редкое копирование O(n) делится на много append. Это не значит «каждый append всегда O(1) без копий».

Пример. Слайс с cap 8. Семь append подряд — дешёвые. Восьмой не влез: выделили массив на 16, скопировали 8 элементов. Дальше снова дёшево. Средняя цена одного append близка к константе, хотя один из них был линейным.

Связь с бэкендом

Константы и железо важны не меньше буквы O. Два линейных прохода по массиву в кэше процессора часто быстрее «асимптотически лучшего» алгоритма, который прыгает по памяти и ловит cache miss.

Планировщик Postgres выбирает Index Scan, когда нужных строк мало. Seq Scan — когда прочитать таблицу целиком дешевле случайных прыжков по индексу. Оба плана линейны по числу прочитанных страниц. Константа random I/O другая.

• O(1) амортизированный append против редкого O(n) копирования при росте массива.
• Поиск в хэш-таблице: средний O(1), худший O(n) при коллизиях.
• Сортировка сравнениями не лучше O(n log n) в худшем случае.
• Бинарный поиск O(log n) только на отсортированных данных. Тот же логарифм у высоты B-tree.