Memecahkan persamaan rekursif $T(n)=T(k)+T(n-k-1)+O(n)$

Question

Pertanyaannya jelas di judulnya. Saya mencoba untuk menyelesaikan rekursi ini sebagai bagian dari menunjukkan bahwa kasus terburuk dari algoritma quicksort terjadi ketika$k=0$, tapi tidak bisa. Saya dapat melakukan kasus khusus berikut (dengan berulang kali menggunakan rekursi yang sama):

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

Adakah yang bisa membantu saya untuk menyelesaikan kasus umum ini (atau setidaknya menyarankan cara lain untuk membuktikan bahwa kasus terburuk adalah $k=0$)?

PS Saya tidak tahu teorema Guru, jadi saya akan menghargai solusi tanpa menggunakan itu (Jika itu berlaku di sini).

Answer 1

Pertimbangkan kekambuhan $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$yang merupakan salah satu formalisasi dari kasus terburuk waktu berjalan quicksort. Mari kita tunjukkan dengan induksi bahwa maksimum dicapai pada$k = 0$ (atau $k = n$). Kami akan menunjukkan ini sekaligus menunjukkan itu$T(n) = \frac{n(n+1)}{2}$.

Kasus dasar, $n=0$, jelas. Sekarang anggaplah begitu$T(m) = \frac{m(m+1)}{2}$ untuk semua $m \leq n$, dan pertimbangkan $T(n+1)$. Fungsinya$T(k)$ adalah cembung pada interval $[0,n]$ (kami memperluasnya ke nilai riil menggunakan rumus yang sama), dan maksimal $T(k) + T(n-k)$ dicapai pada $k=0$ (atau $k=n$). Karena itu$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

Daripada berdebat menggunakan konveksitas, kita juga bisa berdebat secara langsung: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ yang dengan jelas dimaksimalkan (secara unik) saat $k = 0$ atau $k = n$.