Решение рецидива методом подстановки

Question

Изучая алгоритмы и обращаясь к CLRS, я столкнулся с проблемой

T(n) = T(n-a) + T(a) + cn ; a >= 1 and c > 0
it is Big-theta(n^2), can be easily proved by recursion tree method

Я могу решить это методом дерева рекурсии.

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

Я попытался решить это сам, но не могу найти какой-либо шаблон как таковой.

Более того, мое расширение на первом этапе кажется мне несколько неправильным:

T(n) = T(n-2a + T(a) + c(n-1)) + T(a) + cn
T(n) = T(n-3a + 2T(a) + c(n-1)(n-2)) + T(a) + cn

И это, кажется, никуда не денется..

Вы можете решить это методом замены? Каково ваше "предположение"?

Answer 1

Ваша первая строка расширения не годится, но вторая логична (посмотрите внимательно, вы не делали одно и то же дважды в скобках).

Вот как вы можете это сделать:

T(n) = T(n-a) + T(a) + cn
T(n) = T(n-2a) + T(a) + c(n-a) + (T(a) + cn)
     = T(n-2a) + 2T(a) + c(2n-a)
     = T(n-3a) + T(a) + c(n-2a) + (2T(a) + c(2n-a))
     = T(n-3a) + 3T(a) + c(3n - 3a)
...
    = T(n-ka) + kT(a) + ck(n - (k-1)a/2)  // The last part come from n+(n-a)+...+(n-(k-1)a) = k(n - (k-1)a/2)

Обобщая, вы можете увидеть, что на шаге jразлагая T(n-ja) дам тебе T(n-(j+1)a)один новый T(a)и c(n-ja), Затем,

Sum(c(n-ja), j=0..k-1)=c*(k*n - a*Sum(j), j=0..k-1))
                      = c(kn-a*(k-1)k/2)

Что дает вам результат.

принимать k=n/a, ты получаешь:

T(n) = T(0) + nT(a)/a + c(n/a)(n-(n/a-1)a/2)

что дает примерно

T(n) ~ nT(a)/a + c n^2 /(2a)

который Theta(n^2) поскольку c>0,