再帰方程式を解く $T(n)=T(k)+T(n-k-1)+O(n)$
質問はタイトルで明確です。クイックソートアルゴリズムの最悪のケースが次の場合に発生することを示す一環として、この再帰を解決しようとしています。$k=0$、しかしそれを行うことはできません。次の特定のケースを実行できます（同じ再帰を繰り返し使用することにより）。
1）$T(n)=T(n-1)+O(n)$
2）$T(n)=2T(\frac n2)+O(n)$
誰かが私がこの一般的なケースを解決するのを手伝ってくれますか（または少なくとも最悪のケースが $k=0$）？
PSマスターの定理がわからないので、それを使わずに解決策をいただければ幸いです（ここで当てはまる場合）。
回答
再発を考慮してください $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$これは、クイックソートの最悪の場合の実行時間の1つの形式化です。最大値がで達成されることを帰納法で示しましょう$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$。