Цикл внутри цикла
O(n²) означает квадратичное время: объём работы растёт как квадрат размера входных данных. В два раза больше элементов — в четыре раза больше шагов. В десять раз больше элементов — в сто раз больше шагов.
Характерная форма в коде — это цикл внутри цикла, причём оба проходят по одним и тем же данным. Внешний цикл выполняется n раз, и на каждом его шаге внутренний цикл снова выполняется n раз: n · n шагов.
Для небольших срезов квадратичное время вполне приемлемо. Но для 100 000 элементов это уже 10 миллиардов шагов — именно здесь программы начинают зависать.
Все пары
Самая наглядная задача на O(n²): соединить каждый элемент с каждым. 4 буквы дают 4 · 4 = 16 пар; 100 букв дали бы 10 000.
Построить все пары
Внешний цикл выбирает x, внутренний соединяет его с каждым y. 4 элемента дают 16 пар — квадрат размера входных данных.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
letters := []string{"a", "b", "c", "d"}
pairs := 0
for _, x := range letters {
for _, y := range letters {
fmt.Print(x+y, " ")
pairs++
}
fmt.Println()
}
fmt.Println(len(letters), "элемента дали", pairs, "пар")
}
Сортировка пузырьком
Сортировка пузырьком — классический квадратичный алгоритм: он раз за разом проходит по срезу и меняет местами соседей, стоящих в неправильном порядке. Большие значения «всплывают» к концу, по одному проходу за раз.
С двумя вложенными циклами он делает около n²/2 сравнений. На нём отлично учиться — и плохо им пользоваться: slices.Sort() делает ту же работу за O(n log n).
Сортировка двумя вложенными циклами
Сортировка 5 элементов требует 4 + 3 + 2 + 1 = 10 сравнений. Для 1000 элементов их было бы около полумиллиона — тогда как сортировке за O(n log n) нужно около десяти тысяч.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{5, 3, 8, 1, 4}
comparisons := 0
for i := 0; i < len(nums)-1; i++ {
for j := 0; j < len(nums)-1-i; j++ {
comparisons++
if nums[j] > nums[j+1] {
nums[j], nums[j+1] = nums[j+1], nums[j]
}
}
}
fmt.Println("отсортировано:", nums)
fmt.Println("сравнений:", comparisons)
}
Поиск дубликатов медленным способом
Сравнение каждого элемента с каждым, который идёт после него, — ещё один шаблон с вложенными циклами: перебор всех пар, чтобы найти дубликат.
Это работает, но это O(n²). На странице «Пространственная сложность» в этой группе показан стандартный приём, который делает задачу линейной: запоминать уже встреченные значения в map.
Найти дубликат двумя циклами
Каждый элемент сравнивается с каждым последующим. Пара одинаковых единиц находится после 7 проверок; в худшем случае — когда дубликата нет вовсе — выполняются все 15 проверок пар.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9}
checks := 0
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
checks++
if nums[i] == nums[j] {
fmt.Println("дубликат:", nums[i], "после", checks, "проверок")
}
}
}
}