Мастер-метод применим только для алгоритма деления и покоя

Question

Мастер-метод применим только для алгоритма разделения и завоевания равного размера? Не для всех рекурсивных алгоритмов?

Answer 1

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

Итак, если вы не можете разделить заданную проблему на такие подзадачи одинакового размера, то теорема о мастерстве будет недостаточно для того, чтобы помочь вам найти решение. Например, рекуррентное соотношение с T (n), зависящее от T (n-k), например, k, являющееся любым конкретным целым, не может быть действительно разрешено с использованием основной теоремы. Однако подход, использованный в его доказательстве, по-прежнему будет полезен. (т.е. расширение подзадач до тех пор, пока соотношение не зависит только от базовых случаев)