Özyinelemeli denklemi çözme $T(n)=T(k)+T(n-k-1)+O(n)$

Question

Soru başlıkta açık. Quicksort algoritmasının en kötü durumunun ne zaman ortaya çıktığını göstermenin bir parçası olarak bu özyinelemeyi çözmeye çalışıyorum.$k=0$ama yapamazsın. Aşağıdaki özel durumları yapabilirim (aynı özyinelemeyi tekrar tekrar kullanarak):

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

Lütfen herhangi biri bu genel durumu çözmeme yardım edebilir mi (veya en azından en kötü durumun olduğunu kanıtlamak için başka bir yol önerebilir mi?) $k=0$)?

PS Master'ın teoremini bilmiyorum, bu yüzden onu kullanmadan bir çözümü takdir ediyorum (burada geçerli olması durumunda).

Answer 1

Yinelemeyi düşünün $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$bu, quicksort'un en kötü durumdaki çalışma süresinin resmileştirilmesidir. Tümevarımla maksimuma ulaşıldığını gösterelim.$k = 0$ (veya $k = n$). Bunu gösterirken aynı zamanda göstereceğiz$T(n) = \frac{n(n+1)}{2}$.

Temel durum, $n=0$, temiz. Şimdi varsayalım ki$T(m) = \frac{m(m+1)}{2}$ hepsi için $m \leq n$ve düşün $T(n+1)$. İşlev$T(k)$ aralıkta dışbükeydir $[0,n]$ (aynı formülü kullanarak bunu gerçek değerlere genişletiriz) ve böylece maksimum $T(k) + T(n-k)$ ulaşılır $k=0$ (veya $k=n$). Bu nedenle$$ T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}. $$

Dışbükeyliği kullanarak tartışmak yerine, doğrudan şunu da tartışabiliriz: $$ T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} = \frac{n(n+1)}{2}-k(n-k), $$ açıkça maksimize edilen (benzersiz) $k = 0$ veya $k = n$.