Вирішувати рівняння рекуррентів - алгоритм, рекурсія, структури даних, порядок, повторення

Хтось може мені допомогти у вирішенні цього складного рецидиву?

T(N)=N + sigma {  T(N-K)+T(K) }  sigma index k-1 to n

T(1) = 1.

Я плутаюсь із використанням дерева рекурсії та індукції математики.

Відповіді:

Виглядає як повторення середнього часу запуску швидкості. Його рішення - Theta (N log N), ви можете спробувати довести індукцією. Погляньте http://en.wikipedia.org/wiki/Quicksort#Solving_the_recurrence_using_mathematical_induction для більш детальної інформації.