Рассчитать большую сложность задачи разбиения

Question

Мой псевдокод выглядит так:

solve(n)
    for i:= 1 to n do
       process(i);
       solve(n-i);

, где process(n) - функция с некоторой сложностью f(n).В моем случае f(n)=O(n^2), но меня также интересует общий случай (например, если f(n)=O(n)).

Итак, у меня есть T(n) = f(n) + ... + f(1) + T(n-1) + ... + T(1).Я не могу применить теорему Мастера, так как подзадачи имеют разный размер.

Как рассчитать сложность этой рекурсии?

Answer 1

Небольшой трюк - рассмотрим solve(n-1):

solve(n)  :  T(n)   =  f(n) + f(n-1) + f(n-2) + ... + f(1) + T(n-1) + T(n-2) + ... + T(0)
solve(n-1):  T(n-1) =         f(n-1) + f(n-2) + ... + f(1) +          T(n-2) + ... + T(0)

Вычтите последнее из первого:

Расширяйте многократно:

Решите последнее суммирование для f(n), чтобы получить сложность.

, например, для f(n) = O(n):

---

Альтернативный метод - замена переменной:

S(m) в правильной форме для основной теоремы.

например, для f(n) = O(n) = O(log m), используйте Случай 2 с k = 0:

Тот же результат, qed