Алгоритмы и их сложность

На соревновании шесть участников получили штрафы: [7, 4, 9, 2, 8, 3]. Нужно назвать наименьший штраф. На таком списке ответ легко увидеть глазами: это 2. Но если участников 200 000, хочется поручить ту же работу программе. С чего начать, чтобы она выдала нужный результат?

Сначала договоримся о задаче

В условии ищем три вещи: что программе дают, что она должна вернуть и какие данные допустимы. Здесь вход — список штрафов, выход — одно минимальное число, ограничение — от 1 до 200 000 участников. Это наша договорённость о поведении программы; её также называют контрактом.

Только после этого выбираем способ решения. Пройдём по штрафам слева направо: запомним первый, а затем будем заменять его, если встретится меньшее значение. Последовательность таких точно заданных шагов и есть алгоритм. Одну задачу можно решать разными алгоритмами; одна и та же идея может быть записана на разных языках.

Алгоритм — конечная последовательность понятных исполнителю действий, которая для каждого допустимого входа приводит к требуемому результату.

Проверяем граничные случаи

Прежде чем писать код, попробуем идею на самых маленьких и необычных допустимых входах. Такие примеры называют граничными случаями: они проверяют предположения, на которых держится решение. Для одного штрафа ответом будет он сам; для одинаковых штрафов — их общее значение. Если минимум встречается несколько раз, его значение от этого не меняется.

У пустого списка минимального элемента нет. Наше условие запрещает такой вход, потому что n ≥ 1. В другой задаче пустой список может быть разрешён — тогда нужно заранее договориться об отдельном результате. Такие решения принимает условие задачи, а не язык программирования.

От слов к блок-схеме и псевдокоду

Опишем алгоритм независимо от языка. Сначала сохраняем первый элемент. Затем для каждого оставшегося числа проверяем: меньше ли оно сохранённого? Если да — обновляем ответ. Когда числа закончатся, возвращаем ответ. В блок-схеме прямоугольник показывает действие, ромб — проверку, стрелки — порядок шагов; овал обозначает начало или конец, параллелограмм — ввод или вывод.

Псевдокод (pseudocode) — короткая запись шагов алгоритма для человека. Она передаёт идею без синтаксических подробностей конкретного языка.

function minimum(A):
  result := A[0]
  for i := 1; i < len(A); i++:
    if A[i] < result:
      result := A[i]
  return result

Мы умеем описать решение и проверить его на маленьких примерах. Теперь сравним, сколько работы делают разные решения. Для этого сначала договоримся, что считать одним действием компьютера.

Для 1 000 участников можно один раз просмотреть штрафы — около 1 000 шагов. А можно многократно сравнивать участников друг с другом — уже сотни тысяч сравнений. Чтобы увидеть эту разницу, не нужно сначала писать обе программы и измерять секунды.

Секунды зависят от процессора, языка и того, как устроена память. Поэтому для начала считаем простые действия: прочитать число, сравнить два числа, сохранить результат, увеличить счётчик. Договоримся, что каждое такое действие над числом фиксированного размера имеет постоянную стоимость: она не растёт вместе с длиной входного массива.

RAM-модель (Random Access Machine) — упрощённая модель компьютера с пронумерованными ячейками памяти. Чтение или запись одной ячейки по известному адресу, сравнение и простая арифметика над машинными словами считаются элементарными действиями.

Если прочитать ячейку 1, затем 4, затем 7, получатся три чтения. Нам не нужно последовательно проходить все адреса между ними. Но копирование массива из n элементов затрагивает n ячеек: это уже целая последовательность действий.

Попробуйте прочитать и изменить память

В модели ниже сначала выберите ячейку мышью или клавишами Tab и Enter. Кнопка «Прочитать» покажет её значение и увеличит счётчик чтений. Чтобы выполнить запись, введите новое число и нажмите «Записать». Сбросьте модель и прочитайте ячейки 1, 4 и 7: проверьте, что чтений ровно три.

Теперь у действий есть понятная модель стоимости. Посчитаем, как их количество зависит от размера входа на уже знакомом поиске минимума.

В RAM-модели мы договорились считать элементарные действия. Теперь посмотрим, как их число меняется при увеличении входа. Обозначим размер входа буквой n: для массива это число элементов, для строки — число символов. Если на входе одно большое число, размером может быть количество цифр или битов в его записи. Выбор параметра всегда нужно объяснять.

Вернёмся к штрафам [7, 4, 9, 2, 8, 3]. Здесь n = 6. Сохраним первый штраф 7 без сравнения. Затем сравним с ответом 4 — ответ станет 4; число 9 его не изменит; число 2 уменьшит до 2; значения 8 и 3 оставят ответ прежним. Получается пять сравнений, а не шесть.

Проследите весь проход

Модель начинает с уже сохранённого первого элемента. На каждом шаге она сравнивает следующий кандидат с текущим минимумом. Перед нажатием кнопки попробуйте предсказать, изменится ли ответ. Затем вернитесь на шаг назад и проверьте, какие элементы уже просмотрены.

От конкретного прохода к оценке

Первое значение задаёт ответ, остальные n − 1 могут его уточнить. Для 10 элементов будет 9 сравнений, для 1 000 — 999, для 200 000 — 199 999. Чтения, обновления и проверки цикла тоже требуют работы, но на каждый элемент приходится ограниченное число таких действий. При удвоении длины массива объём работы растёт примерно вдвое.

Функцией T(n) обозначают количество учитываемых действий при размере входа n. Для нашего алгоритма оно растёт линейно; коротко пишут O(n). Это описание роста, а не обещание ровно n операций или n секунд. Мы храним лишь текущий ответ и индекс — их число не растёт с n. Поэтому дополнительная память, то есть память сверх входных данных, равна O(1).

Те же шаги в программе

В реализациях ниже предполагается непустой массив. Сначала берём его первый элемент, затем начинаем цикл со второго. Поэтому в цикле ровно n − 1 сравнений. В Python return возвращает результат; в Rust последнее выражение функции играет ту же роль.

def minimum(a):
    result = a[0]
    for i in range(1, len(a)):
        if a[i] < result:
            result = a[i]
    return result

print(minimum([7, 4, 9, 2, 8, 3]))

fn minimum(a: &[i64]) -> i64 {
    let mut result = a[0];
    for &value in &a[1..] {
        if value < result {
            result = value;
        }
    }
    result
}

fn main() {
    println!("{}", minimum(&[7, 4, 9, 2, 8, 3]));
}

2

def minimum(values: list[int]) -> int | None:
    if not values:
        return None
    result = values[0]
    for i in range(1, len(values)):
        value = values[i]
        if value < result:
            result = value
    return result

print(minimum([7, 4, 9, 2, 8, 3]))
print(minimum([]))

fn minimum(values: &[i64]) -> Option<i64> {
    let (&first, rest) = values.split_first()?;
    let mut result = first;
    for &value in rest {
        if value < result {
            result = value;
        }
    }
    Some(result)
}

fn main() {
    println!("{}", minimum(&[7, 4, 9, 2, 8, 3]).unwrap());
    println!("{:?}", minimum(&[]));
}

2
None

function minimum(A):
  result := +Infinity
  for i := 0; i < len(A); i++:
    result := min(result, A[i])
  return result

Один проход растёт линейно. Но алгоритмы могут выполнять и фиксированное число действий, и все пары сравнений. Дадим этим различиям общий язык.

def minimum(a):
	# Напишите решение здесь
	pass

Допустим, один алгоритм делает около 5n действий, а другой — n². При n = 10 это 50 и 100; при n = 100 — 500 и 10 000; при n = 1 000 — 5 000 и 1 000 000. Разница увеличивается вместе с входом. Для выбора идеи обычно важнее увидеть этот рост, чем точно сосчитать каждую служебную операцию.

O-нотация описывает верхнюю границу роста количества работы с точностью до постоянного множителя, начиная с достаточно больших входов. У 5n и 5n + 2 линейный рост O(n); добавление постоянного числа действий не меняет его. Когда говорят о сложности алгоритма, стремятся назвать достаточно точную, полезную оценку.

Что означает логарифм

Число log₂ n отвечает на вопрос: сколько раз нужно поделить n пополам, чтобы получить 1? Для 1 024 это десять делений: 1 024 → 512 → 256 → … → 2 → 1. Основание логарифма в O-нотации обычно не пишут: смена постоянного основания меняет лишь постоянный множитель.

При удвоении n линейная работа примерно удваивается, квадратичная — увеличивается в четыре раза, а логарифмическая получает ещё один шаг. В интерактиве сравниваются модельные функции. Например, n log₂ n может быть нецелым, хотя реальное число действий всегда целое.

Теперь применим язык роста к конкретной сортировке. Начнём с идеи, которую можно выполнить руками, раскладывая карточки.

Представьте карточки [4, 2, 4, 1]. Первую карточку считаем уже упорядоченной. Берём следующую и вставляем в нужное место среди взятых ранее. Это сортировка вставками: отсортированное начало массива растёт на один элемент за шаг.

Вставляем 2 перед первой 4: получается [2, 4, 4, 1]. Следующая 4 уже стоит после значений, не превышающих её, поэтому не двигается. Наконец, 1 проходит влево через все три карточки: [1, 2, 4, 4]. Обе четвёрки сохранены.

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

function insertion_sort(A):
  for i := 1; i < len(A); i++:
    j := i
    while j > 0 and A[j] < A[j-1]:
      swap(A[j], A[j-1])
      j := j - 1

Перед каждым новым элементом в модели выберите индекс, на котором он окажется. Индекс — номер позиции, начиная с нуля. Затем выполняйте соседние обмены по одному и следите за зелёным префиксом. Если ответ пока неверный, сравните вставляемое число с его будущими соседями.

Когда вставки делают много работы

В обратном порядке каждый новый элемент проходит через всё отсортированное начало. Число обменов равно 1 + 2 + … + (n − 1), поэтому худшее время O(n²). На уже отсортированном входе обменов нет, но внешний цикл и сравнения остаются: время O(n). Ноль обменов не означает ноль работы.

def insertion_sort(values: list[int]) -> None:
    for i in range(1, len(values)):
        j = i
        while j > 0 and values[j] < values[j - 1]:
            values[j], values[j - 1] = values[j - 1], values[j]
            j -= 1

data = [5, 2, 4, 2, 1]
insertion_sort(data)
print(data)

fn insertion_sort(values: &mut [i64]) {
    for i in 1..values.len() {
        let mut j = i;
        while j > 0 && values[j] < values[j - 1] {
            values.swap(j, j - 1);
            j -= 1;
        }
    }
}

fn main() {
    let mut data = [5, 2, 4, 2, 1];
    insertion_sort(&mut data);
    println!("{:?}", data);
}

[1, 2, 2, 4, 5]

while j > 0 and a[j] > a[j - 1]:
    a[j], a[j - 1] = a[j - 1], a[j]
    j -= 1

function insertionSort(A):
  for i := 1; i < len(A); i++:
    j := i
    while j > 0 and A[j] < A[j-1]:
      swap(A[j], A[j-1])
      j := j - 1
  return A

Время вставок зависит от порядка данных. Уточним, что такое лучший и худший случай, и научимся считать шаги вложенных циклов без догадок.

def insertion_sort(a):
	# Напишите решение здесь
	pass

Два массива одной длины могут требовать разного времени. При сортировке вставками массив [1, 2, 3, 4] не требует перестановок, а [4, 3, 2, 1] заставляет каждый новый элемент идти в начало. Лучший случай — наименьшая работа среди допустимых входов размера n; худший — наибольшая. Говоря о худшем случае, мы не утверждаем, что каждый запуск будет таким долгим.

Считаем вложенные циклы

Само наличие двух циклов ещё не даёт ответ. Нужно понять, сколько раз выполняется их общее внутреннее действие. Если оба цикла проходят все n элементов, на каждый из n внешних шагов приходится n внутренних. Для n = 5 это 5 × 5 = 25 действий, а в общем случае n².

for i in range(n):
    for j in range(n):
        process(i, j)

Теперь пусть j перебирает только индексы меньше i. При i = 0 действий нет; при i = 1 — одно; при i = 2 — два. Для n = 5 сумма равна 0 + 1 + 2 + 3 + 4 = 10. В общем виде это n(n − 1)/2. Множитель 1/2 уменьшает точное число действий, но рост остаётся квадратичным: O(n²).

for i in range(n):
    for j in range(i):
        process(j, i)

В третьем режиме внешний цикл всё ещё имеет n шагов, а внутренний каждый раз уменьшает k вдвое. Он делает порядка log n шагов, поэтому вместе получается O(n log n). Анализируем границы и изменение переменных, а не количество строк с for.

def count_pairs(n: int) -> int:
    operations = 0
    for i in range(n):
        for _ in range(i):
            operations += 1
    return operations

print(count_pairs(5))
print(count_pairs(0))

fn count_pairs(n: u64) -> u64 {
    let mut operations = 0;
    for i in 0..n {
        for _ in 0..i {
            operations += 1;
        }
    }
    operations
}

fn main() {
    println!("{}", count_pairs(5));
    println!("{}", count_pairs(0));
}

10
0

В примере выше циклы помогают проверить подсчёт на малых n. В задании ниже нужно вернуть только количество пар. При n = 200 000 перечислять почти 20 миллиардов пар неразумно; используйте выведенную формулу. Проверьте и n = 0, и n = 1: в обоих случаях пар нет.

for i := 1; i <= n; i++:
  for j := 1; j*j <= i; j++:
    // действие за O(1)

Цикл явно повторяет действия. Есть и другой способ повторения: функция вызывает саму себя на меньшей задаче. Посмотрим, как такой способ останавливается и сколько работы создаёт.

def count_pairs(n):
	# Напишите решение здесь
	pass

Нужно сложить числа от 1 до 4. Можно заметить: сумма до 4 — это 4 плюс сумма до 3. Та, в свою очередь, равна 3 плюс сумма до 2. Мы сводим задачу к такой же задаче меньшего размера. Если функцию записать через вызов самой себя, получится рекурсия.

function sum_to(n):
  if n = 0:
    return 0
  return n + sum_to(n - 1)

Цепочка вызовов: 4 → 3 → 2 → 1 → 0. На нуле сразу возвращаем 0 — это базовый случай, который не требует нового вызова. Затем ответы собираются обратно: 1 + 0 = 1, 2 + 1 = 3, 3 + 3 = 6, 4 + 6 = 10. Без базового случая функция продолжала бы вызывать себя и после нуля.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(4))

fn sum_to(n: u64) -> u64 {
    if n == 0 {
        return 0;
    }
    n + sum_to(n - 1)
}

fn main() {
    println!("{}", sum_to(4));
}

10

Что происходит при каждом вызове

Каждый вызов хранит свои переменные и ждёт ответа меньшей задачи. В модели ниже видны вход в вызов, достижение базы и возврат к родителю. Начните с n − 1, затем сравните с делением пополам и с двумя вызовами на половинах. Счётчики отдельно показывают глубину текущей ветви и число всех сделанных вызовов.

При уменьшении на 1 путь имеет порядка n переходов. Если каждый раз брать половину, путь короче: 32 → 16 → 8 → 4 → 2 → 1, всего пять переходов. Такая идея используется в бинарном поиске, лекция 05: после сравнения можно отбросить половину кандидатов. Реализовывать его сейчас не требуется.

Но короткий путь ещё не означает мало работы всего. Если каждый вызов создаёт две подзадачи, нужно посчитать обе ветви, а не только одну. Это различие вскоре понадобится для сортировки слиянием.

def binary_search(values: list[int], target: int) -> int | None:
    def search(left: int, right: int) -> int | None:
        if left >= right:
            return None
        mid = left + (right - left) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            return search(mid + 1, right)
        return search(left, mid)
    return search(0, len(values))

print(binary_search([1, 3, 5, 7, 9], 7))
print(binary_search([], 7))

fn binary_search(values: &[i64], target: i64) -> Option<usize> {
    fn search(a: &[i64], target: i64, left: usize, right: usize)
        -> Option<usize>
    {
        if left >= right { return None; }
        let mid = left + (right - left) / 2;
        if a[mid] == target { return Some(mid); }
        if a[mid] < target {
            search(a, target, mid + 1, right)
        } else {
            search(a, target, left, mid)
        }
    }
    search(values, target, 0, values.len())
}

fn main() {
    println!("{}", binary_search(&[1, 3, 5, 7, 9], 7).unwrap());
    println!("{:?}", binary_search(&[], 7));
}

3
None

Мы умеем уменьшать задачу и возвращаться с ответом. Теперь разделим сортировку на две меньшие сортировки. Останется понять, как быстро объединить их результаты.

Сначала решим маленькую задачу: есть два уже отсортированных списка A = [1, 4, 7] и B = [2, 3, 8]. Как получить один отсортированный список? Сравним первые числа: 1 меньше 2, берём 1. Затем сравниваем 4 и 2 — берём 2; далее 4 и 3 — берём 3. Продолжая, получаем [1, 2, 3, 4, 7, 8].

У каждого списка держим указатель — индекс первого ещё не перенесённого элемента. Меньший из двух кандидатов и будет следующим в результате: все следующие за ним числа в его списке не меньше. После переноса двигается только один указатель. Если один список кончился, остаток другого можно дописать без сравнений двух кандидатов.

function merge(A, B):
  i := 0; j := 0; C := []
  while i < len(A) and j < len(B):
    if A[i] <= B[j]:
      append(C, A[i]); i := i + 1
    else:
      append(C, B[j]); j := j + 1
  append remaining A[i:] and B[j:] to C
  return C

В режиме предсказания выберите, из какого списка взять следующий элемент. Неверный выбор не сдвигает указатели: прочитайте объяснение и попробуйте ещё раз. В конце сравните число сравнений с числом переносов — это разные величины.

if ___:
    result.append(a[i])
    i += 1

От слияния к сортировке

Если списки имеют длины n и m, каждый из n + m элементов переносится один раз. Поэтому слияние занимает O(n + m) времени. Это позволяет построить сортировку слиянием: разделить массив на две части, рекурсивно отсортировать каждую, затем слить результаты. База рекурсии — длина 0 или 1: такой массив уже упорядочен.

function merge_sort(A):
  if len(A) <= 1:
    return A
  mid := floor(len(A) / 2)
  left := merge_sort(A[:mid])
  right := merge_sort(A[mid:])
  return merge(left, right)

def merge_sort(values: list[int]) -> list[int]:
    if len(values) <= 1:
        return values.copy()
    mid = len(values) // 2
    left = merge_sort(values[:mid])
    right = merge_sort(values[mid:])
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([8, 3, 6, 2, 7, 1, 5, 4]))

fn merge_sort(values: &[i64]) -> Vec<i64> {
    if values.len() <= 1 { return values.to_vec(); }
    let (a, b) = values.split_at(values.len() / 2);
    let left = merge_sort(a);
    let right = merge_sort(b);
    let mut result = Vec::with_capacity(values.len());
    let (mut i, mut j) = (0, 0);
    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            result.push(left[i]);
            i += 1;
        } else {
            result.push(right[j]);
            j += 1;
        }
    }
    result.extend_from_slice(&left[i..]);
    result.extend_from_slice(&right[j..]);
    result
}

fn main() {
    println!("{:?}", merge_sort(&[8, 3, 6, 2, 7, 1, 5, 4]));
}

[1, 2, 3, 4, 5, 6, 7, 8]

Сортировка слиянием имеет O(n log n) времени даже в худшем случае и требует O(n) дополнительной памяти в обычной реализации с буфером. Почему возникает именно n log n, разберём на дереве в следующей главе. А пока в задании достаточно написать само слияние двух готовых списков.

function merge(A, B):
  i := 0; j := 0; C := []
  while i < len(A) or j < len(B):
    if j == len(B) or
       (i < len(A) and A[i] <= B[j]):
      C.push(A[i]); i := i + 1
    else:
      C.push(B[j]); j := j + 1
  return C

function sort(A):
  n := len(A)
  if n <= 1: return A
  m := floor(n / 2)
  L := sort(A[0:m])
  R := sort(A[m:n])
  return merge(L, R)

Каждое слияние линейно по размеру своих списков. Чтобы оценить всю сортировку, посмотрим на все задачи одного уровня одновременно.

def merge(a, b):
	# Напишите решение здесь
	pass

Возьмём массив из восьми элементов. Сначала есть одна задача размера 8. После разделения — две по 4, затем четыре по 2, затем восемь по 1. На каждом уровне в сумме остаются те же восемь элементов: 8 = 2 × 4 = 4 × 2 = 8 × 1.

Чтобы соединить результаты одного уровня, нужно перенести суммарно порядка восьми элементов. Слияния становятся меньше, но их становится больше — эти изменения компенсируются. Поэтому работа одного уровня растёт пропорционально n.

Нажимайте «Разделить» и проверяйте сумму размеров. Для n = 8 до единичных частей нужны три деления пополам; обратно будет три уровня слияния. Для n = 16 таких уровней уже четыре. Удвоение n добавило один уровень, а не удвоило их число.

Складываем работу уровней

Теперь обобщим: делить n пополам до единицы нужно порядка log₂ n раз. На каждом уровне работа порядка n. Значит, вся сортировка требует O(n log n). Если считать ещё и базовые вызовы на единичных частях, добавится линейная работа, которая не меняет эту оценку.

def level_work(n: int) -> list[int]:
    assert n > 0 and n & (n - 1) == 0
    result = []
    calls, size = 1, n
    while True:
        result.append(calls * size)
        if size == 1:
            return result
        calls *= 2
        size //= 2

print(level_work(8))

fn level_work(n: usize) -> Vec<usize> {
    assert!(n.is_power_of_two());
    let (mut calls, mut size) = (1, n);
    let mut result = Vec::new();
    loop {
        result.push(calls * size);
        if size == 1 { return result; }
        calls *= 2;
        size /= 2;
    }
}

fn main() {
    println!("{:?}", level_work(8));
}

[8, 8, 8, 8]

Этого объяснения достаточно, чтобы пользоваться оценкой сортировки. Следующий необязательный блок обобщает анализ деревьев. Его можно пропустить и сразу перейти к выбору алгоритма по ограничениям.

Открыть общий справочник всех лекций ↗

Участники прислали результаты, и нужно понять, встречается ли одно значение дважды. Самая прямая идея — сравнить каждую пару. Для шести чисел это 15 сравнений; для 200 000 — уже 19 999 900 000, почти 20 миллиардов. На таком входе нужна другая идея.

Отсортируем значения. Равные результаты окажутся рядом, поэтому после сортировки достаточно одного прохода по соседям. Получится O(n log n) вместо O(n²). Оценка помогла выбрать способ до написания большого решения.

Четыре шага перед кодом

1. Прочитайте ограничения. Что обозначает n и чему оно может быть равно? Длина массива и величина его элементов — разные параметры.
2. Придумайте простое решение. Уточните, почему оно верно: например, перебор точно проверит все пары.
3. Подставьте максимальный n в объём работы. Для 200 000 один проход — порядка 200 000 шагов, n log₂ n — около 3,52 миллиона, все пары — почти 20 миллиардов.
4. Если работа слишком велика — меняйте идею. Попробуйте сортировку, уменьшение подзадачи или использование уже найденных результатов. Затем оцените память и проверьте код на неудобных входах.

Калькулятор ниже сравнивает масштабы. Он не переводит действия в секунды: сравнение чисел, сравнение строк и выделение памяти имеют разную стоимость, а языки и компьютеры различаются. Подходящий порядок роста — основание проверить реализацию, а не гарантия прохождения лимита.

При n ≤ 20 перебор пар вполне может быть удобным. При n ≤ 200 000 для минимума достаточно прохода, а для поиска повторов пригодится сортировка. Ограничение само по себе не называет алгоритм: оно помогает оценить идею для конкретной задачи. Если |aᵢ| ≤ 10⁹, это не означает миллиард элементов — проход по-прежнему касается только n чисел.

Осталось собрать навыки вместе: написать короткие функции, обосновать выбор сложности и попробовать задачи с настоящими условиями. Внешние отправки не нужны для зачёта этой лекции.

def minimum(a):
	# Напишите решение здесь
	pass

Уровень 2. Перенесите идею в задачу

Ниже сохранён набор внешних задач с тремя уровнями сложности. После разминки начните с Helpful Maths и Contains Duplicate. Binary Search лучше решить после лекции 05. Звёздочная Reverse Pairs — необязательное продолжение: для завершения лекции она не нужна.

Сначала запишите свой контракт и оценку времени, затем решайте задачу. После успешной отправки объясните, почему идея выдерживает максимальный вход. Подсказки ниже раскрываются отдельно.

Уровни задают рекомендуемый порядок практики после этой лекции. Для LeetCode они совпадают с Easy / Medium / Hard; уровень задачи CSES выбран для этого курса. Ссылки ведут на исходные условия.

Уровень 3. Проверьте понимание без подсказки в условии

Пять коротких проверок ниже объединяют минимум, циклы, рекурсию, слияние и ограничения. Если что-то пока не получается, итог подскажет, какую главу повторить. Повторные попытки не отнимают уже полученный зачёт.

def sum_to(n):
    return n + sum_to(n - 1)