การแก้สมการแบบวนซ้ำ $T(n)=T(k)+T(n-k-1)+O(n)$

Question

คำถามมีความชัดเจนในชื่อเรื่อง ฉันกำลังพยายามแก้ปัญหาการเรียกซ้ำนี้เป็นส่วนหนึ่งของการแสดงให้เห็นว่ากรณีที่เลวร้ายที่สุดของอัลกอริทึม Quicksort เกิดขึ้นเมื่อ$k=0$แต่ไม่สามารถทำได้ ฉันสามารถทำบางกรณีต่อไปนี้ได้ (โดยใช้การเรียกซ้ำเดิมซ้ำ ๆ ):

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

ใครสามารถช่วยฉันแก้ปัญหาทั่วไปนี้ได้ (หรืออย่างน้อยก็แนะนำวิธีอื่นในการพิสูจน์ว่ากรณีที่เลวร้ายที่สุดคือ $k=0$)?

ป.ล.ฉันไม่รู้ทฤษฎีบทของอาจารย์ดังนั้นฉันจะขอบคุณวิธีแก้ปัญหาโดยไม่ต้องใช้สิ่งนั้น (ในกรณีที่สามารถใช้ได้ที่นี่)

Answer 1

พิจารณาการเกิดซ้ำ $$ T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0, $$ซึ่งเป็นหนึ่งในการทำให้เป็นทางการของเวลาทำงานที่เลวร้ายที่สุดของ Quicksort ให้เราแสดงโดยการเหนี่ยวนำว่าบรรลุสูงสุดที่$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$.