बबल की जटिलता

Question

मैंने कई जगहों पर देखा है, बबल प्रकार के लिए जटिलता ओ (एन) है।

लेकिन यह ऐसा कैसे हो सकता है क्योंकि आंतरिक पाश हमेशा एन-आई बार चलाना चाहिए।

for (int i = 0; i < toSort.length -1; i++) { 
      for (int j = 0; j < toSort.length - 1 - i; j++) { 
       if(toSort[j] > toSort[j+1]){ 
        int swap = toSort[j+1]; 
        toSort[j + 1] = toSort[j]; 
        toSort[j] = swap; 
       } 
      } 
     } 

Answer 1

और n-i का "औसत" मान क्या है? n/2

तो यह O(n*n/2) में चलाता है जो O (n)

Answer 2

बाहरी पाश रन n काल से है और प्रत्येक यात्रा भीतरी पाश रन (एनआई) बार, संचालन की कुल संख्या हो सकता है के रूप में माना जाता है एन * (एनआई) = ओ (एन 2) के रूप में गणना की गई।

Answer 3

विभिन्न प्रकार की जटिलताएं हैं - आप बड़े ओ नोटेशन का उपयोग कर रहे हैं, इसका मतलब है कि इस समारोह के सभी मामले कम से कम इस समय जटिलता होंगे।

जैसा कि यह अनंतता तक पहुंचता है, यह मूल रूप से एन^2 समय जटिलता सबसे खराब स्थिति परिदृश्य हो सकता है। समय जटिलता एक सटीक कला नहीं है लेकिन एल्गोरिदम के इस वर्ग के लिए आप किस प्रकार की गति की उम्मीद कर सकते हैं और इसलिए आप बहुत सटीक होने की कोशिश कर रहे हैं।

उदाहरण के लिए सैद्धांतिक समय जटिलता बहुत अच्छी तरह से^^ 2 हो सकती है, भले ही सिद्धांत में यह होना चाहिए कि एन * एन -1 1 जो भी अप्रत्याशित प्रसंस्करण ओवरहेड किया जा सकता है।

Answer 4

यह ओ (एन^2) है, क्योंकि लंबाई * लंबाई।