मानते हुए तत्वों की गणना करना मेरे पास एक एसटीएल set <int> s और int x है, मैं में x से कम तत्वों की संख्या कैसे गिन सकता हूं?सी ++ सेट: मान
मैं O(log n) (या समान; O(n)) से उचित रूप से बेहतर कुछ भी मांग रहा हूं;
मुझे पहले से ही std::distance(s.begin(), s.lower_bound(x)) पता है, लेकिन यह O(n) है, मुझे विश्वास है, क्योंकि set एस यादृच्छिक-पहुंच नहीं हैं।
आपको 'ऑर्डर-आंकड़े पेड़' की आवश्यकता है। यह अनिवार्य रूप से एक संवर्धित (बाइनरी खोज) पेड़ है जो अतिरिक्त ऑपरेशन rank(x) का समर्थन करता है जो आपको तत्व x के रूप में कम या समान कुंजी वाले तत्वों की संख्या देता है। कॉर्मन, लीसरसन, रिवेस्ट, स्टीन में अध्याय 14; "एल्गोरिदम के लिए परिचय" आपको एल्गोरिदमिक पृष्ठभूमि देना चाहिए।
web पर कुछ कार्यान्वयन भी है।
मेरी टिप्पणी का पालन करने के रूप में: लाल-काले बाइनरी खोज पेड़ (सेट के बजाए) का उपयोग करके, यदि प्रत्येक नोड उस नोड में रूट नोड्स की संख्या संग्रहीत करता है (हर बार जब आप नोड डालें/हटाते हैं) तो आप आंकड़े काफी तेजी से "एक्स से अधिक/कम नोड्स की संख्या" प्राप्त कर सकते हैं।
मुझे नहीं लगता कि यह संभव है। आपका एसटीएल सेट एक पेड़-आधारित संरचना है, इसलिए केवल तत्व की उपस्थिति की जांच करना ओ (लॉग एन) है। आपके पेड़ के नोड्स किसी भी क्षेत्र (जहां तक मुझे पता है) में अपने उप-शाखाओं के आकार को स्टोर नहीं करते हैं, इसलिए नोड्स की गिनती के लिए आवश्यक संचालन की संख्या जिसमें कुछ संपत्ति होती है जो पेड़ के निर्माण के लिए उपयोग किए गए नियमों से सीधे पालन नहीं करती है, छोटे नहीं हो सकते इन नोड्स की संख्या से। चूंकि आप पहले से नहीं जानते हैं कि कितने नोड्स x से छोटे मान हैं, सबसे खराब केस प्रदर्शन तब होता है जब सभी नोड्स x से छोटे होते हैं, जिसका अर्थ है ओ (एन) सबसे खराब-मामला जटिलता। यहां तक कि यदि मूल्य एक्स पेड़ में था, तो आपको उस नोड को खोजने के लिए ओ (लॉग एन) ऑपरेशंस की आवश्यकता है, लेकिन फिर उन्हें गिनने के लिए अपने सभी बाएं वंशजों को देखने की आवश्यकता है, इसलिए जटिलता मेल खाने वाले नोड्स की संख्या पर निर्भर करती है जो ओ (एन) सबसे खराब मामले में। शायद पेड़ के नोड्स में अतिरिक्त डेटा के साथ, कोई इससे बेहतर कर सकता है।
आप मानक सी ++ सेट के साथ ऐसा नहीं कर सकते हैं। –
क्यों एक बाइनरी खोज पेड़ का उपयोग नहीं करते हैं जो ऑर्डर आंकड़ों के इन प्रकारों का समर्थन करता है? यदि यह लाल-काला बीएसटी है, तो यह सबसे खराब मामले में भी लॉग (एन) प्रदर्शन की गारंटी देगा। – angelatlarge
@EvgenyKluev एक सहायक डेटा-संरचना के साथ भी नहीं जो एक साथ अद्यतन किया जा सकता है? – Chris