रिकर्सिव एल्गोरिदम के लिए रन-टाइम जटिलताओं

Question

मैंने उच्च और निम्न खोज की है और रन-टाइम जटिलताओं, रिकर्सन और जावा से संबंधित बहुत सारी सामग्री नहीं मिल रही है।

मैं वर्तमान में अपने एल्गोरिदम कक्षा में रन-टाइम जटिलताओं और बिग-ओ नोटेशन सीख रहा हूं, और मुझे रिकर्सिव एल्गोरिदम का विश्लेषण करने में समस्या हो रही है।

private String toStringRec(DNode d) 
{ 
    if (d == trailer) 
     return ""; 
    else 
     return d.getElement() + toStringRec(d.getNext()); 
} 

यह एक पुनरावर्ती विधि कि बस हालांकि एक दोगुना से जुड़े सूची पुनरावृति और तत्वों का प्रिंट आउट जाएगा।

एकमात्र चीज जिसके साथ मैं आ सकता हूं यह है कि इसमें ओ (एन) की रन-टाइम जटिलता है, क्योंकि रिकर्सिव विधि कॉल की संख्या डीएलआईस्ट में नोड्स की संख्या पर निर्भर करेगी, लेकिन मैं अभी भी ' इस जवाब के साथ सहज महसूस नहीं करते हैं।

मुझे यकीन नहीं है कि मुझे d और d.getNext() के अतिरिक्त के लिए लेखांकन होना चाहिए या नहीं।

या मैं सिर्फ ट्रैक से पूरी तरह से बंद हूं और रन-टाइम जटिलता स्थिर है, क्योंकि यह सब से DList में तत्वों को पुनर्प्राप्त कर रहा है?

Answer 1

एल्गोरिदम में आपके द्वारा सुझाए गए ओ (एन) की रन-टाइम जटिलता है। आपकी सूची में इसमें एन आइटम हैं, और एल्गोरिदम प्रत्येक आइटम के लिए एक निश्चित निश्चित कार्य करेगा (जो कि एलिमेंट और अगली एक्सेस है, साथ ही एक नया toStringRec कॉल)। डीएनओडी से एलिमेंट को पुनर्प्राप्त करने में निरंतर समय लगता है, और निरंतर समय को बड़े-ओ नोटेशन में छोड़ दिया जाता है।

रिकर्सिव विधियों (ज्यादातर मामलों में) के बारे में दिलचस्प बात यह है कि वे भी अंतरिक्ष जटिलता में ओ (एन) हैं। एक नई स्टैक प्रविष्टि (विधि में पारित पैरामीटर को स्टोर करने के लिए) प्रत्येक कॉल के लिए toStringRec को बनाया जाता है, जिसे n बार कहा जाता है।

Answer 2

पहली नज़र में, यह पूंछ कॉल का एक सामान्यीकरण tail recursion modulo cons का क्लासिक केस जैसा दिखता है। यह पुनरावृत्तियों की संख्या के साथ एक लूप के बराबर है।

हालांकि, यह इतना आसान नहीं है: यहां मुश्किल बात एक बढ़ती स्ट्रिंग के लिए d.getElement() के अलावा है: यह अपने आप में एक रैखिक आपरेशन है, और यह N बार दोहराया जाता है। इसलिए आपके फ़ंक्शन की जटिलता O(N^2) है।

Answer 3

यदि टी (एन) प्राथमिक संचालन की संख्या है (इस मामले में - जब हम फ़ंक्शन के बॉडी में प्रवेश करते हैं, तो अंदर की किसी भी पंक्ति को सबसे अधिक बार निष्पादित किया जाता है लेकिन दूसरा रिटर्न ओ (1) नहीं होता है)) n तत्वों की एक सूची पर toStringRec बुला, तो

T(0) = 1 - as the only things that happen is the branch instruction and a 
       return 
    T(n) = n + T(n-1) for n > 0 - as the stuff which is being done in the 
       function besides calling toStringRec is some constant time stuff and 
       concatenating strings that takes O(n) time; and we also run 
       toStringRec(d.getNet()) which takes T(n-1) time 

इस बिंदु हम एल्गोरिथ्म की जटिलता का वर्णन किया है पर द्वारा निष्पादित। अब हम टी, टी (एन) = ओ (एन ** 2) के लिए बंद फॉर्म की गणना कर सकते हैं।

Answer 4

यह एक बहुत ही सरल उदाहरण है, लेकिन चाल एक पुनरावृत्ति संबंध को परिभाषित करना है, जो छोटे इनपुट आकारों के संदर्भ में दिए गए इनपुट आकार के रनटाइम का एक कार्य है।इस उदाहरण के लिए, यह सोचते हैं कि काम हर कदम पर किया निरंतर समय सी और उस आधार मामला कोई काम करता है यह सोचते हैं लेता है, यह होगा:

T(0) = 0 
T(n) = C + T(n-1) 

फिर आप प्रतिस्थापन का उपयोग कर एक श्रृंखला को खोजने के लिए समय को चलाने के लिए हल कर सकते हैं :

T(n) = C + T(n-1) = 2C + T(n-2) = 3C + T(n-3) = ... = nC + T(n-n) = nC + 0 = nC 

ओ की परिभाषा से, यह समीकरण ओ (एन) है। यह उदाहरण विशेष रूप से दिलचस्प नहीं है, लेकिन यदि आप विलय के रनटाइम की तरह कुछ देखते हैं या कोई अन्य विभाजन और एल्गोरिदम जीतते हैं तो आप पुनरावृत्ति संबंधों का बेहतर विचार प्राप्त कर सकते हैं।

Answer 5

ऐसे रिकर्सिव एल्गोरिदम के लिए, ऑर्डर की गणना करने के लिए आमतौर पर रिकर्सिव समीकरण लिखना संभव है। टी (एन) के साथ निष्पादित निर्देशों की संख्या दिखाने के लिए यह परंपरागत है। इस उदाहरण में, हमने:

टी (एन) = टी (n - 1) + O (1)

(मान लें कि समारोह निरंतर समय में getElement रन है।) इस समीकरण के समाधान तुच्छता से टी है (एन) = ओ (एन)।

यह सामान्य मामला था। हालांकि, कभी-कभी आप इस समीकरण को लिखने के बिना एल्गोरिदम का विश्लेषण कर सकते हैं। इस उदाहरण में, आप आसानी से तर्क दे सकते हैं कि प्रत्येक तत्व को सबसे अधिक बार एक्सेस किया जाता है, और हर बार कुछ स्थिर समय कार्य किया जाता है; इसलिए, यह नौकरी करने के लिए कुल मिलाकर ओ (एन) लेता है।