अनुक्रमिक खोज की समय जटिलता - एल्गोरिदम, रिकर्सन, समय-जटिलता

मैं चयन प्रकार के लिए समय जटिलता खोजने की कोशिश कर रहा हूं जिसमें निम्नलिखित समीकरण हैं
T(n)=T(n-1)+O(n)

पहले मैं इसकी टी (एन) = टी (एन -1) + एन .. एन हालांकि आसान है माना जाता है ..
लगा T(n-1) = T(n-2) + (n-1) तथा T(n-2) = T(n-3) + (n-2)

यह बनाता है T(n) = (T(n-3) + (n-2)) + (n-1) + n तो यह T(n) = T(n-3) + 3n - 3..

K (3) के बजाय ।। T(n) = T(n-k) + kn - k

और क्योंकि n-k> = 0 .. ==> n-k = 0 तथा n=k

वापस eqaution करने के लिए अपने .. T(n) = T(0)// which is C + n*n - n

जो बनाता है C + n^2 -n.. तो इसका O (n ^ 2) .. क्या मैंने ryt किया है ??

उत्तर:

उत्तर № 1 के लिए 1

हां, आपका समाधान सही है। आप O (n-1), O (n-2) ... और O (n ^ 2) के साथ आ रहे हैं। आप आवेदन कर सकते हैं O(n) + O(n-1) = O(n), लेकिन केवल सूक्ष्मता से। एक श्रृंखला में यह अलग है।

T(n) = (0 to n)Σ O(n - i)

ओ के अंदर ध्यान न दें (), आपका परिणाम हे (n ^ 2)

आपके द्वारा दिया गया पुनरावृत्ति संबंध T(n)=T(n-1)+O(n) चयन सॉर्ट के लिए सही है, जिसमें समग्र समय जटिलता O (n ^ 2) है। इसे देखो संपर्क जांचना

---

जवाब के लिए 0 № 2

In selection sort:

पुनरावृति i में, हम सबसे छोटी शेष प्रविष्टि का सूचकांक न्यूनतम पाते हैं। और फिर एक [i] और एक [मिनट] स्वैप करें।

जैसे कि चयन प्रकार का उपयोग करता है

(n-1)+(n-2)+....+2+1+0 = (n-1)*(n-2)/2 = O(n*n) compares

and exactly n exchanges(swappings).

ऊपर से

और ऊपर दिए गए पुनरावृत्ति संबंध से

=> T(n) = T(n-1)+ O(n)
=> T(n) = T(n-1)+ cn, where c is some positive constant
=> T(n) = cn + T(n-2) + c(n-1)
=> T(n) = cn + c(n-1) +T(n-3)+ c(n-2)

और यह आगे बढ़ता है और हम अंततः प्राप्त करते हैं

=> T(n) = cn + c(n-1) + c(n-2) + ...... c (total no of n terms)
=> T(n) = c(n*(n-1)/2)
=> T(n) = O(n*n)

संपादित करें

इसका हमेशा बेहतर थाटी (n) को cn के रूप में बदलना, जहाँ c कुछ स्थिर है। समीकरण को अधिक आसानी से देखने में मदद करता है।

---