सर्वश्रेष्ठ मामलों में स्वैप और तुलना के लिए द्विआधारी सम्मिलन की जटिलता

Jan 18 2021

बाइनरी इंसर्शन सॉर्ट की जटिलता क्या हो सकती है? और कितने स्वैप और तुलना की जाती है?

यह O(n(LG n))तुलना हो सकती है , लेकिन मुझे यकीन नहीं है। सबसे खराब स्थिति के लिए, यह वास्तव में N^2स्वैप है। सर्वश्रेष्ठ के बारे में क्या?

जवाब

1 wsdookadr Jan 19 2021 at 13:29

आप का लाभ निर्मित इस तरह के रूप में कार्य करता द्वारा तरह आसानी से बाइनरी प्रविष्टि लिख सकते हैं bisect_leftऔर list.pop(..)और list.insert(..):

def bininssort(L):
    n = len(L)
    i,j=0,0
    for i in range(1,n):
        j=i-1
        x=L.pop(i)
        i1=bisect_left(L,x,0,j+1)
        L.insert(i1,x)
    return L

सबसे खराब स्थिति के बारे में, i-thलूप के पुनरावृत्ति के बाद से , हम उप-सरणी के अंदर एक द्विआधारी खोज करते हैं A[0..i], जिसके साथ संचालन 0<=i<nकरना चाहिए log(i), इसलिए अब हम जानते हैं कि हमें स्थान पर एक तत्व i1सम्मिलित करना है और हम इसे सम्मिलित करते हैं, लेकिन सम्मिलन का मतलब है कि हमें उन सभी तत्वों को धकेलना होगा जो इसे दाईं ओर एक स्थिति में रखते हैं, और यह कम से कम n-iसंचालन है (यह n-iसम्मिलन स्थान के आधार पर संचालन से अधिक हो सकता है )। यदि हम इन दोनों को प्राप्त करते हैं\sum_{i=1}^n log(i) + (n-i) = log(n!) + (n*(n+1))/2 ~ n*log(n) + (n*(n+1))/2

(उपरोक्त स्टर्लिंग के सन्निकटन का log(n!)उपयोग किया जा रहा है)

अब विकी पेज कहता है

एक नियम के रूप में, कोई यह मान सकता है कि किसी दिए गए कार्य में उच्चतम-क्रम अवधि उसके विकास की दर पर हावी है और इस प्रकार उसके रन-टाइम ऑर्डर को परिभाषित करता है

इसलिए मुझे लगता है कि निष्कर्ष यह होगा कि सबसे खराब स्थिति में द्विआधारी सम्मिलन प्रकार की O(n^2)जटिलता है।

यह सभी देखें:

  • द्विआधारी खोज का उपयोग करके प्रविष्टि प्रकार
  • द्विआधारी खोज के साथ प्रविष्टि सॉर्ट
  • द्विआधारी सम्मिलन के प्रकार का विश्लेषण
  • द्विआधारी सम्मिलन प्रकार और जटिलता

फिर मैंने यह जांचने की कोशिश की कि यह उलटा ( n,n-1,n-2,..,1) और वैकल्पिक ( 0,n-1,1,n-2,2,n-3,...) सूची में कैसा प्रदर्शन कर रहा है । और मैंने उन्हें अलग-अलग विकास दर के लिए ( माचिस की तीली के मॉड्यूल का उपयोग करके ) फिट किया , यह हिस्सा सिर्फ एक अनुमान है। उलट आदेश को बहुपद समय तक फिट किया गया था, और प्रत्यावर्ती आदेश को क्सीलिनरियर समय के लिए फिट किया गया था

सबसे अच्छा मामला यहाँ समझाया गया है । यदि सूची पहले से ही क्रमबद्ध है, तो भले ही हम कोई स्वैप न करें, फिर भी सभी द्विआधारी खोजों का प्रदर्शन किया जा रहा है, जो आगे बढ़ता है O(n*log(n))

यहाँ उपयोग किया गया कोड इस रिपॉजिटरी में उपलब्ध है।