Insertion sort में एक रनटाइम है जो Ω (एन) (जब इनपुट सॉर्ट किया गया है) और ओ (एन) (जब इनपुट रिवर्स सॉर्ट किया जाता है)। औसतन, यह Θ (एन) में चलता है।औसत मामले में सम्मिलन क्रम Θ (एन^2) क्यों है?
यह क्यों है? औसत मामला ओ (एन लॉग एन) के करीब क्यों नहीं है, उदाहरण के लिए?
इस प्रश्न का उत्तर देने के लिए, आइए पहले यह निर्धारित करें कि हम प्रविष्टि प्रकार के रनटाइम का मूल्यांकन कैसे कर सकते हैं। अगर हम रनटाइम के लिए एक अच्छी गणितीय अभिव्यक्ति पा सकते हैं, तो हम औसत रनटाइम निर्धारित करने के लिए उस अभिव्यक्ति में हेरफेर कर सकते हैं।
महत्वपूर्ण अवलोकन हमें करने की आवश्यकता है कि प्रविष्टि प्रकार का रनटाइम इनपुट सरणी में inversions की संख्या से निकटता से संबंधित है। एक सरणी में एक उलटा तत्वों की एक जोड़ी है [i] और ए [जे] जो गलत सापेक्ष क्रम में हैं - यानी, मैं < जे, लेकिन ए [जे] < ए [i]। उदाहरण के लिए, इस सरणी में:
0 1 3 2 4 5
एक उलटा है: 3 और 2 स्विच किया जाना चाहिए। इस सरणी में:
4 1 0 3 2
6 व्युत्क्रम हैं
इनवर्जनों की एक महत्वपूर्ण संपत्ति यह है कि एक क्रमबद्ध सरणी में इसमें कोई उलटा नहीं है, क्योंकि प्रत्येक तत्व इसके बाद आने वाली हर चीज से छोटा होना चाहिए और इससे पहले आने वाली चीज़ों से बड़ा होना चाहिए।
कारण यह महत्वपूर्ण है कि सम्मिलन क्रम में किए गए कार्यों की मात्रा और मूल सरणी में उलटा संख्या के बीच एक सीधा लिंक है।
आम तौर पर जब काम इस तरह एक समारोह के द्वारा किया की कुल राशि का निर्धारण करने के लिए, हम भीतरी द्वारा किए गए कार्य की अधिकतम राशि निर्धारित कर सकते हैं लूप, फिर बाहरी पाश के पुनरावृत्तियों की संख्या से गुणा करें। यह ऊपरी बाउंड देगा, लेकिन जरूरी नहीं कि एक तंग बंधे हों।कुल काम के लिए खाते में करने के लिए एक बेहतर तरीका है पहचान करने के लिए काम के दो अलग-अलग स्रोतों देखते हैं कि है:
वह बाहरी पाश हमेशा Θ (एन) काम करता है। आंतरिक पाश, हालांकि, काम की एक मात्रा है जो एल्गोरिदम के पूरे रनटाइम में किए गए स्वैप की कुल संख्या के आनुपातिक है। यह देखने के लिए कि लूप कितना काम करेगा, हमें यह निर्धारित करने की आवश्यकता होगी कि एल्गोरिदम के सभी पुनरावृत्तियों में कितने कुल स्वैप किए गए हैं।
यह वह जगह है जहां इनवर्जन आते हैं। ध्यान दें कि जब सम्मिलन क्रमबद्ध होता है, तो यह हमेशा सरणी में आसन्न तत्वों को स्वैप करता है, और यदि वे एक उलटा बनाते हैं तो यह केवल दो तत्वों को स्वैप करता है। तो हम स्वैप करने के बाद सरणी में कुल संख्या में उलटा क्या होता है? ठीक है, रेखांकन, हम इस राशि:
[---- X ----] A[j] A[j+1] [---- Y ----]
यहाँ, एक्स सरणी बदली जोड़ी से पहले आ रहा है का हिस्सा है और वाई सरणी बदली जोड़ी के बाद आने वाले का हिस्सा है।
मान लीजिए कि हम ए [जे] और ए [जे + 1] स्वैप करते हैं। उलटाई की संख्या का क्या होता है? खैर, आइए दो तत्वों के बीच कुछ मनमाने ढंग से उलझन में विचार करें। 6 संभावनाएं हैं:
इसका मतलब है कि एक स्वैप करने के बाद, हम वास्तव में इनवर्जन की संख्या को कम कर देते हैं, क्योंकि केवल आसन्न जोड़ी का उलटा गायब हो गया है। निम्नलिखित कारणों से यह बेहद महत्वपूर्ण है: यदि हम इनवर्तन के साथ शुरू करते हैं, तो प्रत्येक स्वैप संख्या को एक से कम कर देगा। एक बार कोई उलटा नहीं छोड़ा जाता है, कोई और स्वैप नहीं किया जाता है। इसलिए, स्वैप की संख्या इनवर्जनों की संख्या के बराबर होती है!
यह देखते हुए, हम Θ (एन + आई) के रूप में सम्मिलन प्रकार के रनटाइम को सटीक रूप से व्यक्त कर सकते हैं, जहां मैं मूल सरणी के उलटा होने की संख्या है। यह हमारी मूल रनटाइम सीमाओं से मेल खाता है - एक क्रमबद्ध सरणी में, 0 इनवर्जन हैं, और रनटाइम Θ (एन + 0) = Θ (एन), और एक रिवर्स-सॉर्टेड सरणी में, एन (एन -1)/2 उलटा, और रनटाइम Θ (एन + एन (एन -1)/2) = Θ (एन) है। निफ्टी!
तो अब हमारे पास एक विशेष सरणी दिए गए प्रविष्टि प्रकार के रनटाइम का विश्लेषण करने का एक सुपर सटीक तरीका है। चलो देखते हैं कि हम अपने औसत रनटाइम का विश्लेषण कैसे कर सकते हैं। ऐसा करने के लिए, हमें इनपुट के वितरण के बारे में एक धारणा बनाने की आवश्यकता होगी। चूंकि प्रविष्टि क्रम एक तुलना-आधारित सॉर्टिंग एल्गोरिदम है, इनपुट सरणी के वास्तविक मान वास्तव में कोई फर्क नहीं पड़ता; केवल उनके रिश्तेदार आदेश वास्तव में मायने रखता है। निम्नानुसार, मैं यह मानने जा रहा हूं कि सभी सरणी तत्व अलग हैं, हालांकि यदि ऐसा नहीं है तो विश्लेषण इतना अधिक नहीं बदलता है। जब हम वहां जाते हैं तो मैं बताऊंगा कि चीजें कहाँ से निकलती हैं।
इस समस्या को हल करने के लिए, हम प्रपत्र एक्स ij, जहां X ij एक यादृच्छिक चर कि है 1 है की सूचक चर का एक गुच्छा को पेश करने जा रहे हैं एक [i] और एक [जे] एक उलटा और 0 अन्यथा बनाओ। इन चरों में से एन (एन -1)/2 होगा, तत्वों की प्रत्येक विशिष्ट जोड़ी के लिए एक। ध्यान दें कि ये चर सरणी में प्रत्येक संभावित विचलन के लिए खाते हैं।
इन एक्स को देखते हुए, हम एक नया यादृच्छिक चर I परिभाषित कर सकते हैं जो सरणी में उलटाई की कुल संख्या के बराबर है। यह एक्स के के योग द्वारा दिया जाएगा:
मैं = Σ एक्स ij
हम ई [मैं], सरणी में व्युत्क्रम की अपेक्षित संख्या में रुचि रखते हैं। उम्मीद की linearity का उपयोग करना, इस
ई [मैं] = ई [Σ एक्स ij] = Σ ई है [X ij]
तो अब अगर हम का मूल्य प्राप्त कर सकते हैं ई [एक्स आईजे], हम अपेक्षित रनटाइम की अपेक्षित संख्या निर्धारित कर सकते हैं और इसलिए, अपेक्षित रनटाइम!
सौभाग्य से, के बाद से सभी एक्स ij के द्विआधारी सूचक चर हैं, हमारे पास है कि
ई [X ij] = पीआर [X ij = 1] = पीआर [एक [i] और एक [जे] एक व्युत्क्रम हैं]
तो क्या हुआ, कोई डुप्लिकेट के साथ एक यादृच्छिक इनपुट सरणी को देखते हुए संभावना है कि एक [i] और एक [जे] एक व्युत्क्रम कर रहे हैं? खैर, आधे समय, ए [मैं] ए [जे] से कम होगा, और समय के दूसरे आधे ए [i] ए [जे] से अधिक होंगे। (यदि डुप्लिकेट की अनुमति है, तो डुप्लिकेट को संभालने के लिए एक स्नीकी अतिरिक्त शब्द है, लेकिन हम अभी इसके लिए अनदेखा करेंगे)। नतीजतन, संभावना के बीच एक व्युत्क्रम एक ऐसा [i] और एक [जे] 1/2. इसलिए है:
ई [मैं] = Σ ई [X ij] = Σ (1/2)
चूंकि n (n - 1)/4 = Θ (n - 1) राशि में/2 शर्तों, इस बाहर करने के लिए
ई [मैं] = n (एन काम करता है)
और हां, तो उम्मीद पर, वहाँ Θ (एन) व्युत्क्रम है, इसलिए उम्मीद पर क्रम Θ (एन + एन) = Θ (एन) हो जाएगा।यह बताता है कि सम्मिलन क्रम का औसत-मामला व्यवहार Θ (एन) क्यों है।
आशा है कि इससे मदद मिलती है!
मैं गलत हो सकता हूं (और उम्मीद है कि मैं हूं), लेकिन यह मुझे थोड़ा और लगता है प्रविष्टि प्रकार की तुलना में बबल प्रकार की तरह ... मेरा मानना था कि सम्मिलन प्रकार को वर्तमान आइटम के लिए उचित स्थान मिला और बाकी की सूची को इस तरह के तत्वों को स्वैप करने के बजाय नीचे सूचीबद्ध किया गया ... फिर भी, विश्लेषण काफी हद तक है प्रासंगिक, चूंकि बबल सॉर्ट और सम्मिलन क्रम बहुत समान प्रदर्शन-वार हैं। – twalberg
@ twalberg- क्या आप चयन प्रकार के बारे में सोच रहे हैं? मैंने हमेशा इस तरह परिभाषित प्रविष्टि प्रकार देखा है। – templatetypedef
संभवतः ... मैंने छद्म कोड को गलत पढ़ा होगा ... या संभवतः मैं जगह के बजाय बाहर की जगह सम्मिलन प्रकार के बारे में सोच रहा हूं ... मुझे लगता है कि एक जगह में सम्मिलन सम्मिलन प्रकार होगा चीजों को चारों ओर स्थानांतरित करने के लिए उचित रूप से स्वैप का उपयोग करें। – twalberg
अधिकांश एल्गोरिदम औसत-मामले को सबसे खराब मामले के समान होते हैं। यह देखने के लिए कि यह क्यों है, चलो सबसे बुरी स्थिति और Ω सबसे अच्छा मामला कॉल करें। संभवतः, ओ> = Ω एन एन अनंतता में जाता है। अधिकांश वितरणों के लिए, औसत मामला सबसे अच्छे और सबसे बुरे मामले के औसत के करीब होने वाला है - यानी, (ओ + Ω)/2 = ओ/2 + Ω/2। चूंकि हम गुणांक की परवाह नहीं करते हैं, और ओ> = Ω, यह ओ
जैसा ही है, यह एक अतिसंवेदनशीलता है। ऐसे समय वितरण चल रहे हैं जो इस तरह से कमजोर हैं कि औसत मामले की धारणा सबसे बुरी स्थिति का औसत है और सर्वोत्तम मामला मान्य नहीं है *। लेकिन यह आपको एक सभ्य अंतर्ज्ञान देना चाहिए कि यह क्यों है।
* टिप्पणियों में templatetypedef द्वारा उल्लिखित अनुसार, कुछ उदाहरण quicksort/quickselect, बीएसटी लुकअप (जब तक आप पेड़ को संतुलित नहीं करते हैं), हैश टेबल लुकअप, और सरल विधि।
कई महत्वपूर्ण एल्गोरिदम में सबसे खराब-केस रनटाइम होते हैं जो उनके औसत-केस रनटाइम से भिन्न होते हैं: क्विकॉर्ट, क्विकसेलेक्ट, बीएसटी लुकअप, हैश टेबल लुकअप, और सरल विधि को ध्यान में रखना आता है। – templatetypedef
@templatetypedef मुझे यकीन था कि कुछ थे, लेकिन मैं कुछ भी नहीं लेकर आ रहा था। सुझावों के लिए धन्यवाद! –
मज़े के लिए मैंने एक प्रोग्राम लिखा जो आकार के गिनती तुलना के सभी डेटा संयोजनों के माध्यम से चला गया और पाया कि सबसे अच्छा मामला एन -1 (सभी क्रमबद्ध) है और सबसे खराब है (एन * (एन -1))/2।
अलग n के लिए कुछ परिणाम:
n min ave max ave/(min+max) ave/max
2 1 1 1 0.5000
3 2 2.667 3 0.5334
4 3 4.917 6 0.5463
5 4 7.717 10 0.5512
6 5 11.050 15 0.5525
7 6 14.907 21 0.5521
8 7 19.282 28 0.5509
9 8 24.171 36 0.5493
10 9 29.571 45 0.5476
11 10 35.480 55 0.5458
12 11 41.897 66 0.5441
यह औसत मूल्य मिनट करीब की तुलना में यह अधिकतम करता है इस प्रकार है लगता है।
संपादित करें: कुछ अतिरिक्त मान
13 12 48.820 78 0.5424
14 13 56.248 91 0.5408
संपादित करें: के लिए मूल्य 15
15 14 64.182 105 0.5393
संपादित करें: चयनित उच्च मूल्यों
16 15 72.619 120 - 0.6052
32 31 275.942 496 - 0.5563
64 63 1034.772 1953 - 0.5294
128 127 4186.567 8128 - 0.5151
256 255 16569.876 32640 - 0.5077
मैंने हाल ही में एन के उच्च मूल्यों के लिए सम्मिलन प्रकार के लिए तुलना की औसत संख्या की गणना करने के लिए एक कार्यक्रम लिखा है। इनसे मैंने निष्कर्ष निकाला है कि एन अनन्तता के दृष्टिकोण के रूप में औसत मामला दो से विभाजित सबसे खराब मामले तक पहुंचता है।
औसत रनटाइम की वृद्धि दर को देखें। ध्यान दें कि जब इनपुट आकार युगल होता है तो यह चार के कारक से ऊपर जाता है। इसका मतलब यह है कि यह वर्गबद्ध है और इसलिए न्यूनतम से अधिकतम बारीकी से ट्रैक करता है। मैं शर्त लगाता हूं कि यदि आपको बड़े एन के लिए मूल्य मिलते हैं, तो न्यूनतम और औसत के बीच का अंतर बहुत अधिक होगा। – templatetypedef
@templatetypedef मेरी गलती। न्यूनतम और अधिकतम एनएक्स के रूप में 2x और 4x की निरंतर वृद्धि पर स्थिर होता है। एवी डेटा को देखते हुए मैंने निष्कर्ष निकाला कि यह 3.7x के आसपास के क्षेत्र में स्थिर हो जाएगा। –
जो एन^1.888 पर आता है। –
आप अपने प्रश्न का उत्तर दें – nachokk
@nachokk: स्टैक ओवरफ़्लो इसे प्रोत्साहित करता है: http://stackoverflow.com/help/self-answer – templatetypedef