std::set/std::map के माध्यम से पुनरावृत्ति की समय जटिलता क्या है? मेरा मानना है कि यह सेट/मानचित्र के आकार में रैखिक है, लेकिन इतना निश्चित नहीं है। क्या यह भाषा मानक में निर्दिष्ट है?std :: set/std :: map के माध्यम से पुनरावृत्ति की समय जटिलता क्या है?
draft C++11 standard N3337 में जवाब § में पाया जा सकता है 24.2.1 पैरा 8:
सभी iterators की श्रेणियों केवल उन कार्यों है कि एक के लिए वसूली योग्य हैं की आवश्यकता होती है निरंतर समय में श्रेणी (amortized) दिया गया।
के बाद से पुनरावर्तक पर प्रत्येक ऑपरेशन निरंतर समय होना चाहिए, n तत्वों के माध्यम से पुनरावृत्ति O(n) होना चाहिए।
यदि नक्शा/सेट को मूल बिंदुओं के साथ बाइनरी पेड़ के रूप में कार्यान्वित किया जाता है, तो सभी तत्वों के माध्यम से पुनरावृत्ति प्रत्येक पेड़ नोड को अधिकतम 3 बार देखेंगी। यदि कार्यान्वयन पैरेंट पॉइंटर्स के साथ एक बी-पेड़ है, तो प्रत्येक नोड का सबसे अधिक 2 * एन + 1 बार, नोड में तत्वों की संख्या का दौरा किया जाएगा। दोनों मामलों में, यह प्रत्येक पुनरावृत्ति चरण के लिए निरंतर औसत समय जटिलता का तात्पर्य है। मैं मानचित्र/सेट को लागू करने के किसी अन्य अनुपालन तरीकों से अवगत नहीं हूं। – WaltK
मुझे विश्वास है कि यह सेट/मानचित्र के आकार में रैखिक है, लेकिन सुनिश्चित नहीं है।
यह सही है। एक पूरे सेट या मानचित्र के माध्यम से पुनरावृत्ति O(N)
एक संपूर्ण कंटेनर का इटरेशन हमेशा 'ओ (एन) '_at कम से कम होगा (मुझे लगता है कि वास्तव में मूर्खतापूर्ण कार्यान्वयन इसे _worse_ बना सकता है) – Chad
जब आप कहते हैं कि" पुनरावृत्ति ", तो आपका क्या मतलब है? क्या आप एक मानक इटरेटर का उपयोग कर थोड़ी देर/लूप लिख रहे हैं? क्या आप मानक एल्गोरिदम में से एक का उपयोग कर रहे हैं? –