Основная теорема с Log n рекомбинацией

Question

Как я понимаю основную теорему, алгоритм может быть определен рекурсивно как:

a T(n/b) + O(n^d)

Где a - количество подзадач, n/b - размер подзадач, а O(n^d) - время рекомбинации подзадач. Расчет временной сложности основной теоремы происходит следующим образом:

T(n) =  { O(n^d)                    if d > log base b of a
        {
        { O(n^d log n)              if d = log base b of a
        {
        { O(n^ (log base b of a) )  if d < log base b of a

У меня вопрос, а что, если время рекомбинации не выражается в форме O(n^d)? Например, O(2^n) или O(log(n)). Как определить сложность времени?

Answer 1

С теоремой Мастера это не так, она применима только к рецидивам определенной формы. Ты говоришь:

Как я понимаю основную теорему, алгоритм может быть определен рекурсивно как:

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

Для других форм существуют другие теоремы, такие как эта.