बबल सॉर्ट ओ (एन^2) क्यों है?

Question

int currentMinIndex = 0; 

for (int front = 0; front < intArray.length; front++) 
{ 
    currentMinIndex = front; 

    for (int i = front; i < intArray.length; i++) 
    { 
     if (intArray[i] < intArray[currentMinIndex]) 
     { 
      currentMinIndex = i; 
     } 
    } 

    int tmp = intArray[front]; 
    intArray[front] = intArray[currentMinIndex]; 
    intArray[currentMinIndex] = tmp; 
} 

आंतरिक लूप पुनरावृत्ति है: एन + (एन -1) + (एन -2) + (एन -3) + ... + 1 बार।

बाहरी पाश पुनरावृत्ति है: एन बार।

तो तुम n *

कि n * (एन * (n + 1)/2) नहीं है (संख्या n करने के लिए 1 का योग) मिल = n * ((एन^2) + एन/2)

कौन सा होगा (एन^3) + (एन^2)/2 = ओ (एन^3)?

मैं सकारात्मक हूं मैं यह गलत कर रहा हूं। ओ क्यों नहीं है (एन^3)?

Answer 1

आप सही हैं कि बाहरी पाश एन बार पुनरावृत्त करता है और आंतरिक पाश एन बार भी पुनरावृत्त करता है, लेकिन आप काम को दोगुना कर रहे हैं। यदि आप शीर्ष-स्तरीय पाश के प्रत्येक पुनरावृत्ति में किए गए कार्यों को संक्षेप में किए गए कुल कार्य को गिनते हैं तो आपको लगता है कि पहला पुनरावृत्ति एन काम करता है, दूसरा एन -1, तीसरा एन -2, आदि, ith के बाद से शीर्ष-स्तरीय पाश के पुनरावृत्ति में आंतरिक लूप n - i काम कर रहा है।

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

आप इन दो रणनीतियों को गठबंधन करने का प्रयास कर एक त्रुटि कर रहे हैं। यह सच है कि बाहरी पाश पहली बार काम करता है, फिर एन -1, फिर एन -2, इत्यादि। हालांकि, आप कुल प्राप्त करने के लिए इस काम को एन से गुणा नहीं करते हैं। यह प्रत्येक पुनरावृत्ति एन बार गिनती होगी। इसके बजाय, आप उन्हें एक साथ जोड़ सकते हैं।

आशा है कि इससे मदद मिलती है!

Answer 2

भीतरी पाश दोहराता n बार (सबसे खराब स्थिति में):

for(int i = front; i < intArray.length; i++) 

बाहरी पाश दोहराता n बार:

for(int front = 0; front < intArray.length; front++) 

इसलिए O (n^2)

Answer 3

ही आपको मानसिक लूप पुनरावृत्त कर रहा है, कुल मिलाकर, जैसा आपने कहा था एन + (एन -1) + (एन -2) + (एन -3) + ... + 1 बार। तो यह ओ (एन + (एन -1) + (एन -2) + (एन -3) + ... + 1) = ओ (एन (एन + 1)/2) = ओ (एन^2) है

Answer 4

कैसे आप मूल रूप से एन ... गणना

• प्रत्येक पंक्ति: +1

• प्रत्येक लूप * एन

  तो तुम जोड़ना शुरू संख्या आपकी पहली पाश के लिए मिलता है अब आप एन है + 1, आप आगे बढ़ते रहते हैं और अंततः आप समय के साथ एन * एन या एन^2 प्राप्त करते हैं। नंबर बंद खींच के रूप में यह एन

सुंदर ज्यादा एन तरह की 1,2,3 ... एन पाश वस्तु के रूप में मौजूद सभी आइटम का प्रतिनिधित्व है की तुलना में आम तौर पर नगण्य है। तो यह बस एक संख्या का प्रतिनिधित्व कर रहा है कि लूप, लूप कितनी बार नहीं।

Answer 5

बस बबल प्रकार के कुछ पायथन संस्करण होने के लिए ...

def bubble_sort(input): 
    n = len(input) 
    iterations = 0 
    for i in xrange(n, 1, -1): 
     for j in range(0, i - 1): 
      iterations += 1 
      if input[j] > input[j+1]: 
       input[j],input[j+1] = input[j+1],input[j] 

    print iterations 
    return input 

कुल पुनरावृत्ति को गिनने के लिए आंतरिक लूप में इटरेशन जोड़ा गया था। बबल प्रकार के साथ कुछ भी नहीं करने के लिए।

5 तत्वों की एक सरणी पास करना, परिणाम 15 पुनरावृत्तियों में 25 नहीं हैं। इसके अलावा जब पूर्व-क्रमबद्ध होने पर भी 15 पुनरावृत्तियों का परिणाम होता है। लेकिन जटिलता को तुलना और स्वैपिंग को भी ध्यान में रखना चाहिए।

Answer 6

k=1(sigma k)n = n(n+1)/2 
because: 
    s = 1 + 2 + ... + (n-1) + n 
    s = n + (n-1) + ... + 2  + 1 
+) 
=================================== 
    2s = n*(n+1) 
    s = n(n+1)/2 
in bubble sort, 
(n-1) + (n-2) + ... + 1 + 0 times compares 
which means, k=0(sigma k)n-1 
, k=0(sigma k)n-1 equals [k=1(sigma k)n] - n 
therefore, n(n+1)/2 - n = n(n-1)/2 
which is 1/2(n^2-n) => O(1/2(n^2-n)) 
in big O notation, we remove constant, so 
O(n^2-n) 
n^2 is larger than n 
O(n^2)