Алгоритмы: рекуррентные отношения из CLRS

Question

Недавно я пытался решить некоторые рекуррентные отношения из CLRS, и я заметил странный нюанс при решении этих уравнений. Я не знаю, заметил ли кто-нибудь из вас это или нет, или, возможно, чемпионы Теории могут пролить больше света на это. (У меня тоже есть степень по CS, но не по теории!). При решении рекуррентности по основной теореме:

T (n) = a T (n / b) + f (n)

Я заметил, что рассуждение выглядит примерно так:

i) разверните арийное дерево рекурсии, и мы получим ^{log _b n} листовых узлов, где работа, выполненная для узла, равна Θ (1), давая Θ (n ^{log _b a} ) для всех конечных узлов

ii) для всех неконечных узлов g (n) = Σa ^j f (b / n ^j ), где j суммирует от 0 до этажа (log * 1021) * b n - 1), где высота дерева равна log _b n

iii) Теперь сделайте прыжок веры: заявите, что f (n) действительно ограничено O (n ^{log _b a} - & epsilon;) для некоторых & epsilon; > 0

iv) Теперь решите g (n) в терминах f (n) и T (n) в терминах g (n). Как упомянуто в шаге i, T (n) действительно Θ (n ^{log _b a} ) + g (n), поэтому, как только у вас получится, что g (n) объединится с другим срок, чтобы придумать T (n)

Проблема, с которой я сталкиваюсь при таком подходе, состоит в том, что здесь рассуждение выглядит примерно так: посмотрите, если мы предположим, что правая часть равна X, то мы включим это в уравнение, чтобы решить левую часть. Разве это не немного странно? Разве это не так:

Дано: X ² = 8X - 16

так что давайте предположим, что X = 4 и поместим это в RHS и решим для X, круто, видите, мы получили 4 !!! Это определенно интересно, но вы действительно решаете проблему - почему вы не догадались, что X - иррациональное число, а не мнимое число?

Более того, я бы на самом деле хотел бы знать, в какой области математики существует этот тип рассуждений, так как я подозреваю, что он пришел к CS из этой области. Любая идея? Я знаю, что почти 99% математики в CS - это просто «более причудливая форма аргументов при определенных допущениях» (так как специализация CS не решает уравнения в общепринятом смысле), но все же этот метод кажется очень уникальным. Есть идеи?

Answer 1

Забавный шаг в прыжке с веры - это ярлык для математической индукции.По сути, это выглядит так:

• Убедитесь, что предположение верно для некоторого базового случая (например, только для одного неконечного узла).
• Учитывая, что оно верно для n -й не базовый случай, убедитесь, что это верно для n+1 -го неосновного случая.

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

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