मैंने सुना है कि यह हे (एन) के समय में एक दोगुना से जुड़े सूची पर द्विआधारी खोज को लागू करना संभव है। एक दोगुनी-लिंक्ड सूची के यादृच्छिक तत्व तक पहुंचने से ओ (एन) समय लगता है, और बाइनरी खोज ओ (लॉग एन) विभिन्न तत्वों तक पहुंच जाती है, इसलिए रनटाइम इसके बजाय ओ (एन लॉग एन) नहीं होना चाहिए?ओ (एन) समय में दोगुनी-लिंक्ड सूची पर बाइनरी खोज करना संभव कैसे है?
यह कहना (एन एन लॉग इन करें) है कि एक दोगुना से जुड़े सूची पर द्विआधारी खोज के क्रम हे है तकनीकी रूप से सही है, लेकिन वह एक तंग ऊपरी सीमा नहीं है। द्विआधारी खोज और एक अधिक चालाक विश्लेषण के थोड़ा बेहतर कार्यान्वयन का उपयोग करके, ओ (एन) समय में चलाने के लिए बाइनरी खोज प्राप्त करना संभव है।
द्विआधारी खोज के पीछे मूल विचार है निम्नलिखित:
एक दोगुना से जुड़े सूची सूचकांक की गणना प्रत्येक यात्रा (बस सरणी मामले में) की तरह पर देखने के लिए द्वारा काम करेगा पर द्विआधारी खोज का एक अनुभवहीन कार्यान्वयन, तो कम से शुरू करने से हर एक का उपयोग सूची के सामने और उचित संख्या में कदम स्कैनिंग। यह वास्तव में बहुत धीमी है। तत्व सरणी के अंत में है के लिए खोजा जा रहा है, तो सूचकांक ऊपर देखा काम सबसे खराब स्थिति में किया संक्षेप n/2, 3n/4, 7n/8, आदि हो सकता है, हम
मिलn/2 + 3n/4 + 7n/8 + 15N/16 + ... (Θ (लॉग n) पदों)
≥ n/2 + n/2 + ... + n/2 (Θ (लॉग n) पदों)
= Θ (एन लॉग इन करें n)
एक nd
n/2 + 3n/4 + 7n/8 + 15N/16 + ... (Θ (लॉग n) पदों)
≤ n + n + ... + n (Θ (लॉग n) पदों)
= Θ (n n लॉग इन करें)
इसलिए, इस एल्गोरिथ्म के लिए बुरी से बुरी हालत समय जटिलता Θ है (एन एन लॉग इन करें)।
हालांकि, हम अपने दृष्टिकोण के साथ अधिक चालाक होने के कारण Θ (लॉग एन) के कारक द्वारा इसे गति दे सकते हैं। पिछले एल्गोरिदम धीमा होने का कारण यह है कि हर बार जब हमें तत्व देखने की आवश्यकता होती है, तो हम सरणी की शुरुआत से खोज शुरू करते हैं। हालांकि, हमें ऐसा करने की आवश्यकता नहीं है।मध्य तत्व को पहली बार देखने के बाद, हम पहले से ही सरणी के बीच में हैं, और हम जानते हैं कि अगला लुकअप जो हम करने जा रहे हैं वह या तो स्थिति n/4 या 3n/4 पर होगा, जो केवल दूरी एन/4 जहां से हमने छोड़ा था (अगर हम सरणी की शुरुआत से शुरू करते हैं तो एन/4 या 3 एन/4 की तुलना में)। क्या होगा अगर हम सूची के मोर्चे पर फिर से शुरू करने के बजाय, हमारी स्थिति (एन/2) से अगली स्थिति में वापस निकल जाएंगे?
यहां हमारा नया एल्गोरिदम है। सरणी के बीच स्कैन करके शुरू करें, जिसके लिए n/2 चरणों की आवश्यकता होती है। फिर, निर्धारित करें कि सरणी के पहले भाग के मध्य में या सरणी के दूसरे भाग के बीच में तत्व पर जाना है या नहीं। स्थिति n/2 से वहां पहुंचने के लिए केवल n/4 कुल चरणों की आवश्यकता होती है। वहां से, तत्व युक्त सरणी की चौथाई के मध्य बिंदु पर जाकर केवल एन/8 कदम होते हैं, और वहां से सरणी के आठवें के मध्य बिंदु तक जाकर तत्व युक्त केवल एन/16 कदम होते हैं, इसका मतलब है इसका मतलब है कि दिया जाता है चरणों की कुल संख्या
n/2 + n/4 + n/8 + n/16 + द्वारा ...
= n (1/2 + 1/4 + 1/8 + ...)
≤ n
यह foll इस तथ्य से ows कि अनंत ज्यामितीय श्रृंखला 1/2 + 1/4 + 1/8 + ... 1 है। इसलिए, सबसे खराब मामले में कुल कार्य केवल Θ (एन), जो बहुत बेहतर है Θ (एन लॉग एन) से पहले से सबसे खराब मामला।
एक अंतिम विवरण: आप ऐसा क्यों करेंगे? आखिरकार, यह तत्व के लिए दोगुनी-लिंक्ड सूची खोजने के लिए पहले ही ओ (एन) समय लेता है। इस दृष्टिकोण का एक बड़ा फायदा यह है कि भले ही रनटाइम ओ (एन) है, हम केवल ओ (लॉग एन) कुल तुलना (बाइनरी खोज के एक चरण) को समाप्त कर देते हैं। इसका मतलब है कि यदि तुलना महंगा है, तो हम सामान्य रैखिक खोज करने से बाइनरी खोज का उपयोग करके कम काम कर सकते हैं, क्योंकि ओ (एन) तुलना करने वाले काम के बजाए सूची में चलने वाले काम से आता है।