चलने का समय (बड़ा ओ)) एक एल्गोरिदम

Question

मैं इस एल्गोरिदम के लिए चलने का समय की गणना कर रहा हूं?

       Cost  No Of Times 

for(j=1;j<=n-1;j++){   c1  n(loop will run for n-1 times +1 for failed cond    

    for(i=0;i<=n-2;i++){  c2  n*(n-1) (n-1 from outer loop and n for inner 

     if(a[i]>a[i+1]){  c3  (n-1)*(n-1) 

      Swap    c4  (n-1)*(n-1) {in worst case } 
     } 
    } 

सबसे खराब स्थिति में टी (एन) = c1 * n + c2 * (n-1) n + सी 3 (n-1) (n-1) + सी 4 * (n- 1) (n-1) जो O (n^2)

बेस्ट मामले में है:

टी (एन) = c1 * n + c2 * (n-1) n + सी 3 (एन -1) (एन -1) जो ओ (एन^2) है।

लेकिन वास्तव में सबसे अच्छे मामले में बबल सॉर्ट में समय जटिलता ओ (एन) है। क्या कोई समझा सकता है?

Answer 1

बबल सॉर्ट में ओ (एन) समय की जटिलता सबसे अच्छी स्थिति में है क्योंकि इसे पहले से क्रमबद्ध सूची पास करना संभव है।

आपको यह जांचना है कि आपने दूसरे नेस्टेड लूप के बाद कोई स्वैप किया है या नहीं। यदि कोई स्वैप नहीं किया गया है, तो सूची क्रमबद्ध की जाती है और जारी रखने की कोई आवश्यकता नहीं है, इसलिए आप लूप को तोड़ सकते हैं।

पहले से क्रमबद्ध सूची के लिए, आप इस मामले में एक बार सभी एन तत्वों पर पुनरावृत्त हो गए होंगे।

Answer 2

बुलबुला तरह लागू करने के लिए अपने algo सही लेकिन कुशल नहीं है,

// n elments की कुल संख्या है

do{ 

    swp = false // swp checks whether or not any variable has been swapped 
         in the inner loop 

     for(i=0;i<=n-2;i++){ 

        if(a[i]>a[i+1]) 

        { 
         swap(a[i],a[i+1]) 

         sw = true 
        } 
     n = n-1    
    }while(sw == true && n>0) 

SWP एक चर जो की जाँच करता है में किसी भी स्वैप कर दिया गया है कि क्या है आंतरिक लूप या नहीं,
यदि कोई स्वैप नहीं किया गया है तो इसका मतलब है कि हमारी सरणी सॉर्ट की गई है।

बुलबुला प्रकार के लिए सबसे अच्छा मामले में जब तत्वों को पहले ही आरोही क्रम में सॉर्ट कर रहे हैं (इस मामले में)
जिसके लिए भीतरी पाश सिर्फ एक बार चलता है, लेकिन हालत अगर (भीतरी पाश में) संतुष्ट नहीं है और है swp झूठ बना रहता है और इस प्रकार हम बाहरी लूप से एक पुनरावृत्ति के बाद बाहर निकलते हैं जो बबल प्रकार ओ (एन) जटिलता देता है।

Answer 3

आप पुनरावृत्तियों की संख्या की गणना कर सकते हैं (क्या पाश अंदर अप्रासंगिक है यह निरंतर समय की है, क्योंकि) का उपयोग कर सिग्मा संकेतन:

एक सबसे अच्छा मामले के साथ बुलबुला क्रमबद्ध समय चल रहा है वास्तव में एक उन्नत संस्करण है इस सॉर्टिंग एल्गोरिदम के।

पहले पार्स (बाहरी पाश) के दौरान, यदि कोई स्वैप नहीं किया गया था, तो यह एक निर्णायक जानकारी है जिसे सरणी सॉर्ट किया गया है, और यह सभी मामलों को कवर करने के लिए व्यर्थ है।

इसलिए, बाहरी पाश एक बार पुनरावृति होता है, और भीतरी पाश n बार पुनरावृति होगा: कि n + 1 पुनरावृत्तियों समग्र ==>हे (एन) है।