Введение в алгоритмы Третье издание - Упражнение 2.3 -3 - Индуктивное доказательство nlg(n)

Question

Я читаю книгу "Введение в алгоритмы", третье издание. В упражнении нас просят использовать индуктивное мышление, чтобы доказать

T(n) = {2 if n = 2, 2T(n/2) + n if n > 2^k for k > 1} = nlgn

Где lg - база журнала 2. Книга предлагает решение:

Base Case:
n = 2, T(2) = 2, 2lg(2) = 2

Assumption:
T (n/2) = (n/2)lg(n/2)

Induction:
T (n) = 2T (n/2) + n
= 2(n/2)lg(n/2) + n
= n(lg n − 1) + n
= n lg n − n + n
= n lg n

Может ли кто-нибудь объяснить, почему значение n/2 используется на этапе Предположения? С моим пониманием индукции я бы использовал значение 2^n а затем увеличил его до 2^(n+1) чтобы покрыть все возможные полномочия 2. Я хочу знать, почему я не прав. Кроме того, кто-то может объяснить операции, которые меняются 2(n/2)lg(n/2)+n into n(lg n-1) + n? Это не придерживается математических соглашений, о которых я знаю.

Answer 1

Приступая к некоторым основным математике:

lg (a / b) = lg (a) - lg (b)

Это причина, почему:

2 (n / 2) lg (n / 2) + n = n (lg (n) - lg (2)) + n = n (lg (n) - 1) + n

Что касается предположения n / 2, это предположение является наилучшим предположением, поскольку оно упрощает шаг индукции. На шаге индукции мы достигаем результата легко и без какого-либо строгого математического объяснения.

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