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)
- 1. std :: map में find() की समय जटिलता?
- 2. ट्रीसेट पुनरावृत्ति की समय जटिलता क्या है?
- 3. क्या std :: map ज्ञात (और मानक द्वारा गारंटीकृत) के माध्यम से पुनरावृत्ति का क्रम है?
- 4. std :: map
- 5. std :: map
- 6. std :: map
- 7. std :: map
- 8. std :: map को std :: C++
- 9. random.sample की समय जटिलता
- 10. "पुनरावृत्ति" तरीकों के माध्यम से
- 11. मैं std :: map
- 12. std :: map :: find()
- 13. क्लोजर में गिनती कार्य की समय जटिलता क्या है?
- 14. इस स्ट्रिंग के माध्यम से पुनरावृत्ति करते समय मुझे सेगमेंटेशन गलती क्यों मिलती है?
- 15. योजना में इस कार्य की समय जटिलता क्या है?
- 16. पेड़ के ट्रैवर्सल की समय जटिलता क्या है?
- 17. std :: context_wrapper का उपयोग std :: map
- 18. क्या वेक्टर की जटिलता :: स्पष्ट अनिर्दिष्ट है?
- 19. std :: सूची बनाम std :: वेक्टर पुनरावृत्ति
- 20. स्मृति आवंटन की समय जटिलता
- 21. हैश टेबल की समय जटिलता
- 22. std :: map iterator कैसे काम करता है?
- 23. std :: कतार पुनरावृत्ति
- 24. नींद की तरह की जटिलता क्या है?
- 25. फ्लेरी के एल्गोरिदम की समय जटिलता
- 26. OrderedDictionary की जटिलता क्या है?
- 27. एल्गोरिदम की कंप्यूटिंग समय जटिलता पर संसाधन
- 28. std :: जोड़ी की एक क्रमबद्ध std :: सूची को कैसे परिवर्तित करें :: std :: map
- 29. रूबी में ऐरे # यूनिक विधि की समय जटिलता क्या है?
- 30. समय जटिलता
एक संपूर्ण कंटेनर का इटरेशन हमेशा 'ओ (एन) '_at कम से कम होगा (मुझे लगता है कि वास्तव में मूर्खतापूर्ण कार्यान्वयन इसे _worse_ बना सकता है) – Chad
जब आप कहते हैं कि" पुनरावृत्ति ", तो आपका क्या मतलब है? क्या आप एक मानक इटरेटर का उपयोग कर थोड़ी देर/लूप लिख रहे हैं? क्या आप मानक एल्गोरिदम में से एक का उपयोग कर रहे हैं? –