Суть Читай реальные фрагменты кода, считай шаги, выводи Big-O по времени и памяти, предсказывай поведение и находи баг сложности или корректности.
Высота — путь к senior
НольJuniorMiddleSenior
Ты на middle-высоте — в небе
◷ 14 min
Анализ закрепляется, только когда делаешь его на реальном коде. Прочитай каждый фрагмент, посчитай циклы и память и определи сложность — ровно тот ход, который делаешь на ревью пул-реквеста или оценивая решение.
Цель
Отработай цикл, который запускаешь на любой незнакомой функции: найди доминирующую работу, перемножь вложенные циклы, отдели время от памяти и замечай, когда проблема вовсе не в скорости, а в баге корректности.
Фрагмент 1 — во что обходится вложенность?
function countCloserPairs(points, threshold) { let count = 0; for (let i = 0; i < points.length; i++) { for (let j = i + 1; j < points.length; j++) { if (Math.abs(points[i] - points[j]) < threshold) { count++; } } } return count;}
Викторина
Completed
Каковы сложности по времени и памяти у countCloserPairs на n точках?
Heads-up Тут два вложенных цикла, поэтому время O(n²), а не O(n). А память считает структуры данных, а не значение count — три скалярные переменные это O(1).
Heads-up Он проверяет ~n² пар, но никогда их не хранит — лишь инкрементирует счётчик. Память O(1); n² — это время, а не память.
Heads-up Старт j с i+1 уменьшает константу вдвое (n(n−1)/2 вместо n²), но доминирующий член всё равно n². Это O(n²), а не O(n log n).
Фрагмент 2 — предскажи число сравнений
function linearSearch(arr, target) { for (let i = 0; i < arr.length; i++) { if (arr[i] === target) return i; } return -1;}// arr = [0, 1, 2, ..., 999] (1000 отсортированных элементов)
Викторина
Completed
Для arr = [0..999] какое утверждение про linearSearch верно?
Heads-up Отсортированность не делает линейный проход логарифмическим — этот код игнорирует порядок и проверяет каждый элемент. Чтобы использовать сортировку и получить O(log n), нужен бинарный поиск.
Heads-up Лучший случай — 1 (цель на индексе 0); худший — n (цель в конце или отсутствует). Среднее ~n/2, но Big-O сообщает худший случай, O(n).
Heads-up Ранний возврат помогает, только когда цель близка к началу. Для отсутствующего значения или значения в конце он сканирует все n элементов — худший случай O(n).
Фрагмент 3 — один результат, разная стоимость
// Версия Afunction sumToNLoop(n) { let sum = 0; for (let i = 1; i <= n; i++) sum += i; return sum;}// Версия Bfunction sumToNFormula(n) { return n * (n + 1) / 2;}
Викторина
Completed
Обе функции возвращают одно значение. Как соотносятся их сложности?
Heads-up Версия B не вычисляет никакой суммы — она применяет замкнутую формулу n(n+1)/2 за константное число операций. Результат совпадает, но стоимость O(1), а не O(n).
Heads-up Зависеть от ЗНАЧЕНИЯ n — не то же, что масштабироваться с n. B делает те же несколько арифметических операций, будь n равно 5 или 5 миллиардам — это O(1).
Heads-up Цикл, ограниченный n, выполняется n раз, поэтому это O(n), а не O(1). Лишь цикл с фиксированной границей, независимой от n, — константное время.
Фрагмент 4 — баг, который тест может пропустить
function average(numbers) { let sum = 0; for (let i = 0; i < numbers.length; i++) { sum += numbers[i]; } return sum / numbers.length;}
Викторина
Completed
Сложность в порядке — время O(n), память O(1). Но какой крайний случай ломает корректность и почему это здесь важно?
Heads-up O(n) осуществим для огромных входов — это не баг корректности. Дефект — случай пустого массива, дающий NaN, независимо от размера.
Heads-up Отрицательное среднее — вполне допустимый результат для отрицательных входов — никакого бага. Настоящий крайний случай — пустой массив с делением на ноль.
Heads-up Прохождение тестов — не доказательство корректности. Автор просто не тестировал пустой массив, где длина 0 делает деление NaN.
Итог
Снимать сложность с кода — фиксированный приём: найди доминирующую работу и оставь только этот член; перемножай вложенные циклы и складывай последовательные фазы; считай структуры памяти, а не итерации цикла, для памяти; и помни, что замкнутая формула может заменить цикл O(n) на O(1). Затем проверь вторую ось — алгоритм с идеальной Big-O всё ещё может быть неверен на крайнем случае (пустой вход, деление на ноль), которого твои тесты не коснулись.