Подстановка: угадать и доказать индукцией

Если умеешь доказать оценку рекуррентности подстановкой (угадать форму, предположить для n/2, подставить) - листай до «Теперь сам».

Как думаешь, доказали ли мы n·log n

Дерево подсказало: T(n) = 2·T(n/2) + n это Θ(n·log n). Но «подсказало» - не «доказало»: мы на глаз сложили уровни, на глаз сосчитали их число, на глаз учли листья. А что, если где-то ошиблись на множитель? Нужен способ проверить ответ строго, без картинок. Он есть, и это индукция: предположить, что оценка верна для входов поменьше, и вывести её для n.

На что это похоже

Это ровно индукция из раздела про правильность, только шаг идёт по размеру входа. Рекурсивный вызов T(n/2) читается как «расписка на n/2 уже погашена ровно на столько, сколько мы утверждаем». Подставляешь это обещание в формулу для n и проверяешь, что арифметика сходится - что для n выходит не больше обещанного. Сошлась - оценка доказана для всех n сразу.

Механизм: угадать, предположить, подставить

Три шага. Угадать форму ответа - T(n) ≤ c·n·log₂ n для какой-то константы c. Предположить индукцией, что она верна для меньших входов, в частности для n/2: T(n/2) ≤ c·(n/2)·log₂(n/2). Подставить это в рекуррентность и показать, что для n неравенство держится:

T(n) = 2·T(n/2) + n
     ≤ 2·[c·(n/2)·log₂(n/2)] + n      (подставили предположение)
     = c·n·log₂(n/2) + n
     = c·n·(log₂ n - 1) + n            (log₂(n/2) = log₂ n - 1)
     = c·n·log₂ n - c·n + n
     = c·n·log₂ n - (c-1)·n
     ≤ c·n·log₂ n                      при c ≥ 1

Последний шаг закрывает индукцию: (c-1)·n ≥ 0 при c ≥ 1, поэтому вычитаемое -(c-1)·n неположительно и только уменьшает левую часть. Значит она тем более не больше c·n·log₂ n, и отбрасывание этого слагаемого сохраняет неравенство ≤. Итог: T(n) ≤ c·n·log₂ n для всех n - T(n) = O(n·log n), доказано.

Правило

Подстановка: (1) угадай форму ответа с неизвестной константой; (2) предположи, что она верна для меньших входов; (3) подставь в рекуррентность и подбери константу так, чтобы неравенство для n замкнулось. Плюс проверь базу. Дерево даёт догадку, подстановка - доказательство.

Разбор: база не на единице

У доказательства есть тонкость с базой. При n = 1 оценка c·n·log₂ n = c·1·0 = 0, а T(1) - положительная константа, 0 ≥ T(1) неверно. Значит база на единице не годится. Берут базу побольше - n = 2: T(2) это какая-то константа, а c·2·log₂ 2 = 2c, и c берут настолько большим, чтобы 2c ≥ T(2). Индукция же всё равно применяется к n ≥ 4 (сводит к n/2 ≥ 2), поэтому маленькие входы можно закрыть выбором c. Асимптотика про большие n, и стартовать индукцию с двойки, а не с единицы, - законно.

Разбор: подстановка ловит неверную догадку

Пусть кто-то предположил, что T(n) = 2·T(n/2) + n это O(n) - линия. Проверим подстановкой: предположим T(n/2) ≤ c·(n/2), тогда

T(n) ≤ 2·c·(n/2) + n = c·n + n = (c+1)·n

Вышло (c+1)·n, а надо было c·n - на n больше, чем обещали. Замкнуть не удаётся ни при каком c: лишнее +n не исчезает. Значит догадка O(n) неверна, и подстановка это показала честно, без картинок. Именно поэтому ей доверяют больше, чем дереву: она либо смыкается, либо нет, и «на глаз» тут ничего не спрячешь.

Верная догадка c·n·log₂ n смыкается ровно потому, что при подстановке лишним выходит −(c−1)·n - слагаемое со знаком минус, которое неравенство только усиливает. У заниженной c·n лишнее слагаемое +n идёт с плюсом и тянет за верхнюю границу. Знак этого остатка и есть тот сигнал, по которому подстановка отличает угаданное верно от угаданного мало.

Что ломается без этого

Три ловушки. Угадать форму верно, но забыть, что константу надо ПОДОБРАТЬ, - и бросить доказательство на середине. Пропустить проверку базы - тогда «доказанное» не опирается ни на что. И самая коварная: доказывать O(n), отбрасывая по дороге лишнее +n как «младшее слагаемое», - в подстановке так нельзя, доказывать надо ровно ту форму, что угадал, до последнего слагаемого. Лишнее +n - это и есть сигнал, что догадка мала.

Зачем это в работе

Дерево быстрое, но обманчивое: легко сбиться в числе уровней или проглядеть листья. Подстановка - страховка: угадал деревом, доказал подстановкой. На практике так и делают - прикинули порядок по дереву за минуту, а если цена ошибки высока (критический алгоритм, оценка в статье), закрыли индукцией начисто. Две техники работают в паре, а не порознь.

Теперь сам

Докажи подстановкой, что T(n) = T(n/2) + 1 (двоичный поиск) это O(log n).

T(n) = T(n/2) + 1 ≤ c·(log₂ n - 1) + 1 = c·log₂ n - c + 1 ≤ c·log₂ n при c ≥ 1