इंटरपोलेशन खोज में प्रत्येक तुलना के बाद सूची की लंबाई sqrt (n) को क्यों कम करती है?

Question

पुस्तक के अनुसार मैं पढ़ रहा हूं, इंटरपोलेशन खोज औसत मामले में O(loglogn) लेती है।
पुस्तक मानती है कि प्रत्येक तुलना n से sqrt(n) तक सूची की लंबाई को कम करती है। खैर, इस धारणा को देखते हुए O(loglogn) को काम करना मुश्किल नहीं है।
हालांकि, पुस्तक ने इस धारणा के बारे में और बात नहीं की, सिवाय इसके कि यह कहता है कि यह सही है।

प्रश्न: क्या कोई इस बारे में कुछ स्पष्टीकरण दे सकता है कि यह सच क्यों है?

Answer 1

यह समान रूप से वितरित इनपुट पर निर्भर करता है (इस तरह की धारणा के बिना, ओ (लॉग एन) सैद्धांतिक रूप से आप कर सकते हैं, यानी बाइनरी खोज इष्टतम है)। एक समान वितरण के साथ, भिन्नता sqrt (n) के आसपास है, और अपेक्षित मामले में प्रत्येक पुनरावृत्ति लक्ष्य के भिन्नता के भीतर हिट होती है। इस प्रकार, जैसा कि आप कहते हैं, खोज स्थान प्रत्येक पुनरावृत्ति पर n -> sqrt (n) से जाता है।

Answer 2

एक सॉर्टेड सरणी की कल्पना करें जहां प्रत्येक प्रविष्टि एक से दस लाख तक की संख्या है। आप देखना चाहते हैं कि 10000 सरणी में है या नहीं। जैसा कि 10000 एक लाख से भी कम संख्या में 99% से कम है, यदि सरणी में संख्याओं का अच्छा वितरण होता है, तो संभावना है कि 10000 की प्रविष्टि, अगर यह सरणी में है, तो शुरुआत के बहुत करीब है। यदि हम सरणी के माध्यम से 1% प्रतिशत प्रविष्टि देखते हैं, और पाते हैं कि यह 10000 से अधिक है, तो हमने एक ही चरण में 99% सरणी को हटा दिया है। यह एक बाइनरी खोज से काफी बेहतर है, जो केवल अंतराल के बीच में दिखता है, और इसलिए एक समय में केवल खोज स्थान के आधा भाग को खत्म कर सकता है। यह सहजता से है कि क्यों कुछ मामलों में इंटरपोलेशन खोज द्विआधारी खोज से कहीं अधिक तेज हो सकती है।

कारण है कि यह हे होने की उम्मीद है की कठोर विश्लेषण देखने के लिए (लॉग लॉग ऑन एन) आप एक पाठ्यपुस्तक या एल्गोरिथ्म पर पेपर के माध्यम से पढ़ने के लिए होगा।