Цикл внутри цикла
O(n²) означает квадратичное время: объём работы растёт как квадрат входных данных. Вдвое больше элементов — вчетверо больше шагов. В десять раз больше элементов — в сто раз больше шагов.
Характерная форма в коде — это цикл внутри цикла, и оба проходят по одним и тем же данным. Внешний цикл выполняется n раз, и для каждого из них внутренний цикл снова выполняется n раз: n · n шагов.
Для маленьких массивов квадратичное время вполне нормально. Для 100 000 элементов это уже 10 миллиардов шагов — именно здесь программы начинают зависать.
Все пары
Самая прямая задача на O(n²): соединить каждый элемент с каждым элементом. 4 буквы дают 4 · 4 = 16 пар; 100 букв дали бы 10 000.
Строим каждую пару
Внешний цикл выбирает x, внутренний соединяет его с каждым y. 4 элемента дают 16 пар — квадрат размера входных данных.
Вывод: программа на TypeScript и захваченный вывод
const letters = ["a", "b", "c", "d"]
let pairs = 0
for (const x of letters) {
const row: string[] = []
for (const y of letters) {
row.push(x + y)
pairs++
}
console.log(row.join(" "))
}
console.log(letters.length, "элементов дали", pairs, "пар")
Сортировка пузырьком
Сортировка пузырьком — классический квадратичный алгоритм: он раз за разом проходит по массиву и меняет местами соседей, стоящих в неверном порядке. Большие значения «всплывают» к концу, по одному проходу за раз.
С двумя вложенными циклами он делает около n²/2 сравнений. Это отличный алгоритм, чтобы на нём учиться, и плохой, чтобы его использовать: nums.sort((a, b) => a - b) делает ту же работу за O(n log n).
Сортировка двумя вложенными циклами
Сортировка 5 элементов занимает 4 + 3 + 2 + 1 = 10 сравнений. Для 1 000 элементов это было бы около полумиллиона — тогда как сортировке за O(n log n) нужно около десяти тысяч.
Вывод: программа на TypeScript и захваченный вывод
const nums = [5, 3, 8, 1, 4]
let comparisons = 0
for (let i = 0; i < nums.length - 1; i++) {
for (let j = 0; j < nums.length - 1 - i; j++) {
comparisons++
if (nums[j] > nums[j + 1]) {
const left = nums[j]
nums[j] = nums[j + 1]
nums[j + 1] = left
}
}
}
console.log("отсортировано:", nums)
console.log("сравнений:", comparisons)
Дубликаты медленным способом
Сравнение каждого элемента с каждым элементом, который идёт после него, — ещё один шаблон вложенных циклов: сравниваем все пары, чтобы найти дубликат.
Это работает, но это O(n²). Страница о пространственной сложности в этой группе показывает стандартный приём, который делает такой поиск линейным: запоминайте уже встреченные значения в Map.
Поиск дубликата двумя циклами
Каждый элемент сравнивается с каждым последующим элементом. Пара одинаковых единиц находится после 7 проверок; в худшем случае — когда дубликата нет вовсе — выполняются все 15 проверок пар.
Вывод: программа на TypeScript и захваченный вывод
const nums = [3, 1, 4, 1, 5, 9]
let checks = 0
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
checks++
if (nums[i] === nums[j]) {
console.log("дубликат:", nums[i], "после", checks, "проверок")
}
}
}