재귀 방정식 풀기 $T(n)=T(k)+T(n-k-1)+O(n)$

Dec 31 2020

질문은 제목에서 분명합니다. 퀵 정렬 알고리즘의 최악의 경우가 발생할 때 발생한다는 것을 보여주는 일환으로이 재귀를 해결하려고합니다.$k=0$,하지만 할 수 없습니다. 동일한 재귀를 반복적으로 사용하여 다음과 같은 특정 경우를 수행 할 수 있습니다.

1)$T(n)=T(n-1)+O(n)$
2)$T(n)=2T(\frac n2)+O(n)$

누구든지이 일반적인 경우를 해결하도록 도와 주실 수 있습니까? (또는 최악의 경우가 $k=0$)?

추신 나는 석사 정리를 모르기 때문에 그것을 사용하지 않고 해결책을 고맙게 생각합니다 (여기에 해당되는 경우).

답변

2 YuvalFilmus Dec 31 2020 at 21:11

재발 고려 $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$이는 퀵 정렬의 최악의 실행 시간을 공식화 한 것입니다. 최대 값에 도달했음을 귀납법으로 보여 드리겠습니다.$k = 0$ (또는 $k = n$). 우리는 이것을 동시에 보여줄 것입니다.$T(n) = \frac{n(n+1)}{2}$.

기본 케이스, $n=0$, 명확합니다. 이제$T(m) = \frac{m(m+1)}{2}$ 모든 $m \leq n$, 고려 $T(n+1)$. 함수$T(k)$ 간격에서 볼록하다 $[0,n]$ (동일한 공식을 사용하여 실제 값으로 확장합니다.) $T(k) + T(n-k)$ 에 달성됩니다 $k=0$ (또는 $k=n$). 따라서$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

볼록성을 사용하여 논쟁하는 대신 다음과 같이 직접 논쟁 할 수도 있습니다. $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ 명확하게 최대화됩니다 (고유). $k = 0$ 또는 $k = n$.