Идея метода замещения заключается в том, чтобы связать функцию, определяемую повторением, с помощью сильной индукции.Я собираюсь предположить, что T(n) - это верхняя граница количества сравнений, которые сортировка слияний использует для сортировки n элементов и определения ее следующим повторением с граничным условием T(1) = 0.
T(n) = T(floor(n/2)) + T(ceil(n/2)) + n - 1.
* 1006.* Cormen et al.используйте
n вместо
n - 1 для простоты и читерства, используя
floor дважды.Давайте не будем обманывать.
Пусть H(n) будет гипотезой, что T(n) ≤ c n lg n.Технически мы должны выбрать c прямо сейчас, поэтому давайте установим c = 100.Cormen et al.выберите запись операторов, которые сохраняются для каждого (положительного) c, пока не станет ясно, каким должен быть c, что является оптимизацией.
Базовые случаи: H(1) и H(2), а именноT(1) ≤ 0 и T(2) ≤ 2 c.Хорошо, нам не нужно никаких сравнений для сортировки одного элемента, и T(2) = T(1) + T(1) + 1 = 1 < 200.
Индуктивно, когда n ≥ 3, предположим для всех 1 ≤ n' < n, что H(n') выполнено.Нам нужно доказать H(n).
T(n) = T(floor(n/2)) + T(ceil(n/2)) + n - 1
≤ c floor(n/2) lg floor(n/2) + T(ceil(n/2)) + n - 1
by the inductive hypothesis H(floor(n/2))
≤ c floor(n/2) lg floor(n/2) + c ceil(n/2) lg ceil(n/2) + n - 1
by the inductive hypothesis H(ceil(n/2))
≤ c floor(n/2) lg (n/2) + c ceil(n/2) lg ceil(n/2) + n - 1
since 0 < floor(n/2) ≤ n/2 and lg is increasing
Теперь нам нужно разобраться с последствиями нашей честности и привязанности lg ceil(n/2).
lg ceil(n/2) = lg (n/2) + lg (ceil(n/2) / (n/2))
< lg (n/2) + lg ((n/2 + 1) / (n/2))
since 0 < ceil(n/2) ≤ n/2 + 1 and lg is increasing
= lg (n/2) + log (1 + 2/n) / log 2
≤ lg (n/2) + 2/(n log 2)
by the inequality log (1 + x) ≤ x, which can be proved with calculus
Хорошо, вернемся к ограничению T(n).
T(n) ≤ c floor(n/2) lg (n/2) + c ceil(n/2) (lg (n/2) + 2/(n log 2)) + n - 1
since 0 < floor(n/2) ≤ n/2 and lg is increasing
= c n lg n - c n + n + 2 c ceil(n/2) / (n log 2) - 1
since floor(n/2) + ceil(n/2) = n and lg (n/2) = lg n - 1
≤ c n lg n - (c - 1) n + 2 c/log 2
since ceil(n/2) ≤ n
≤ c n lg n
since, for all n' ≥ 3, we have (c - 1) n' = 99 n' ≥ 297 > 200/log 2 ≈ 288.539.
Комментарий
Полагаю, это не очень хорошо объясняет причину, но (надеюсь), по крайней мере, выводы правильны во всех деталях.Люди, которые пишут такие доказательства, часто пропускают базовые случаи и игнорируют floor и ceil, потому что, как правило, детали - это просто раздражение, которое влияет на константу c (которую большинству компьютерных ученых, не называемых Кнутом, все равноо).
Для меня метод подстановки - это подтверждение предположения, а не его формулировка.Интересный вопрос: как придумать догадку?Лично, если рецидивом является (i) не то, что выглядит как Фибоначчи (например, линейные однородные рецидивы) и (ii) не охвачено Akra – Bazzi , обобщением основной теоремы,у меня возникнут проблемы с правильным предположением.
Кроме того, я должен упомянуть наиболее распространенный способ отказа метода подстановки: если вы не можете выбрать c достаточно большим, чтобы глотатьдополнительные термины из подзадач, тогда оценка может быть неправильной.С другой стороны, может быть достаточно больше базовых случаев.В предыдущем доказательстве я использовал два базовых случая, потому что не смог доказать самое последнее неравенство, если не знал, что n > 2/log 2.