पुनरावर्ती समीकरण को हल करना $T(n)=T(k)+T(n-k-1)+O(n)$

Question

शीर्षक में प्रश्न स्पष्ट है। मैं यह दिखावा करने की कोशिश कर रहा हूं कि यह दिखाने का एक हिस्सा है कि क्विकसॉर्ट एल्गोरिथम का सबसे खराब मामला कब होता है$k=0$, लेकिन ऐसा नहीं कर सकते। मैं निम्नलिखित विशिष्ट मामलों (एक ही पुनरावृत्ति का बार-बार उपयोग करके) कर सकता था:

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

क्या कोई भी इस सामान्य मामले को हल करने में मेरी मदद कर सकता है (या कम से कम किसी और तरीके से यह साबित करने के लिए सुझाव दे सकता है कि सबसे खराब मामला है $k=0$)?

PS मुझे मास्टर की प्रमेय का पता नहीं है, इसलिए मैं इसका उपयोग किए बिना एक समाधान की सराहना करूंगा (उस स्थिति में जो यहां लागू है)।

Answer 1

पुनरावृत्ति पर विचार करें $$ 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$।