एल्गोरिथम पुस्तकों के अनुसार, द्विआधारी खोज का प्रदर्शन ओ (लॉग एन) है जबकि साधारण खोज के लिए यह ओ (एन) है।

लेकिन हम सॉर्टिंग में लगने वाले समय को भी ध्यान में क्यों नहीं रखते हैं जो बाइनरी सर्च के लिए एक पूर्वापेक्षा है?

2
Mandroid 16 जून 2019, 13:47

2 जवाब

सबसे बढ़िया उत्तर

संक्षेप में: क्योंकि आमतौर पर उस सूची का निर्माण केवल एक बार किया जाता है, जबकि खोज (और अद्यतन) कई बार किया जाता है।

क्रमबद्ध सूची बनाने के लिए वास्तव में O(n log n) की आवश्यकता होती है। द्विआधारी खोज का उपयोग करने की बात यह है कि एक बार संग्रह को क्रमबद्ध करने के बाद, हम उस सूची में एकाधिक क्वेरी कर सकते हैं, प्रत्येक O(log n) के साथ।

इसके अलावा यदि आप उदाहरण के लिए बाइनरी सर्च ट्री का उपयोग करते हैं, तो आप O(log n) में तत्वों को सम्मिलित करना और हटाना भी कर सकते हैं, इसलिए संग्रह को अपडेट करना सस्ता हो सकता है साथ ही (यदि आप उसके लिए एक प्रभावी डेटा संरचना का उपयोग करते हैं)।

उदाहरण के लिए एक डेटाबेस में तेजी से लुकअप करने के लिए अक्सर इंडेक्स का उपयोग किया जाता है। आमतौर पर अपडेट की संख्या की तुलना में पढ़ने की संख्या बड़ी होती है। किसी एक तत्व को अपडेट करने के लिए O(log n) की आवश्यकता होती है, इसलिए मौजूदा डेटा पर इंडेक्स बनाना वास्तव में महंगा है, लेकिन यह B-tree डेटास्ट्रक्चर [विकी]

2
Willem Van Onsem 16 जून 2019, 13:54

यह माना जाता है कि डेटा पहले से ही सॉर्ट किया गया संग्रहीत किया जाएगा। चूंकि हर बार खोज की जाने पर डेटा को फिर से क्रमबद्ध करने की आवश्यकता नहीं होती है, इसलिए इसे बिग ओ में शामिल नहीं किया जाता है।

1
Quentin 16 जून 2019, 13:50