गैलप खोज समय जटिलता?

Question

Gallop search एक क्रमबद्ध सूची में एक तत्व खोजने के लिए है। जब तक आप अपने लक्ष्य को ओवरहूट नहीं करते हैं, तब तक आप इंडेक्स 0, 2, 4, 4, 8, 16 इत्यादि पर इंडेक्स 0 पर एक तत्व लेना शुरू करते हैं, फिर आप उस श्रेणी में फिर से खोजते हैं जिसे आपने अभी पाया था।

इस समय की जटिलता क्या है? ऐसा लगता है कि मुझे कुछ प्रकार की लॉगरिदमिक समय जटिलता है, लेकिन मैं यह नहीं समझ सकता कि क्या।

Answer 1

बुरी से बुरी हालत व्यवहार पर नज़र देता है (कृपया नीचे मेरी संपादित करें देखें)। खोज 0, 1, 2, 4, 8 से जारी है .... कहें कि n है 2^k के लिए कुछ k> = 0. सबसे खराब मामले में हम 2^के तक खोज समाप्त कर सकते हैं और महसूस करते हैं कि हम ओवरशॉट करते हैं लक्ष्य। अब हम जानते हैं कि लक्ष्य 2^(के -1) और 2^के में हो सकता है। उस श्रेणी में तत्वों की संख्या 2^(के -1) है (एक सेकंड सोचो।)। अब तक जिन तत्वों की हमने जांच की है, उनकी संख्या ओ (के) है जो ओ (लॉगन) है। निम्नलिखित पुनरावृत्ति इसे सारांशित करता है।

T(n) = T(n/2) + O(logn) 
    = T(n/4) + c1log(n/2) + c2logn ((all logs are base 2.)) 
    . 
    . 
    . 
    . 
    = O((logn)^2) 

तो इस एल्गोरिदम की सबसे बुरी स्थिति जटिलता लॉगऑन का वर्ग है। यह शायद सबसे सख्त बाध्य नहीं है लेकिन यह एक अच्छा ऊपरी बाउंड है।

संपादित करें: मुझे गलती है। मैंने लिंक का पालन किये बिना सचमुच यहां दी गई गैलप खोज की परिभाषा ली है। लिंक कहता है, एक बार हम ओवरहूट करते हैं, हम पिछले अंतराल में बाइनरी खोज करते हैं। लक्ष्य को ओवरशूट करने के लिए लॉग (एन) समय लगता है और सॉर्ट किए गए अंतराल में बाइनरी खोज करने के लिए लॉग (एन) समय लगता है। यह ओ (लॉग (एन)) एल्गोरिदम बनाता है। टिप्पणियों में इसे इंगित करने के लिए Sumudu Fernando पर धन्यवाद। मैं इसकी सराहना करता हूं।