पायथन सेट ऑपरेशंस की समय जटिलता?

Question

Big O नोटेशन में प्रत्येक पाइथन के सेट ऑपरेशंस की समय जटिलता क्या है?

मैं बड़ी संख्या में वस्तुओं पर एक ऑपरेशन के लिए पायथन के set type का उपयोग कर रहा हूं। मैं जानना चाहता हूं कि प्रत्येक ऑपरेशन का प्रदर्शन सेट के आकार से कैसे प्रभावित होगा। उदाहरण के लिए, add, और सदस्यता के लिए परीक्षण के लिए:

myset = set() 
myset.add('foo') 
'foo' in myset 

चारों ओर Googling किसी भी संसाधनों को चालू नहीं किया गया है, लेकिन यह उचित लगता है कि अजगर के सेट लागू करने के लिए समय जटिलता ध्यान से विचार किया गया होगा।

यदि यह मौजूद है, तो this जैसे किसी लिंक का लिंक बहुत अच्छा होगा। अगर ऐसा कुछ भी नहीं है, तो शायद हम इसे काम कर सकते हैं?

की सभी जटिलता को खोजने के लिए अतिरिक्त अंक सेट ऑपरेशन।

Answer 1

ऑपरेशन in कंटेनर के आकार से स्वतंत्र होना चाहिए, यानी। ओ (1) - एक इष्टतम हैश फ़ंक्शन दिया गया। यह पाइथन स्ट्रिंग के लिए लगभग सत्य होना चाहिए। हैशिंग स्ट्रिंग हमेशा महत्वपूर्ण होती है, पाइथन वहां चालाक होना चाहिए और इस प्रकार आप निकटतम परिणामों की अपेक्षा कर सकते हैं।

Answer 2

Python wiki: Time complexity के अनुसार, सेटhash table के रूप में लागू किया गया है। तो आप ओ (1) औसत में लुक/डालने/हटाने की उम्मीद कर सकते हैं। जब तक आपके हैश टेबल का लोड कारक बहुत अधिक न हो, तब तक आप टकराव और ओ (एन) का सामना करें।

पीएस किसी कारण से वे O (n) को डिलीट ऑपरेशन के लिए दावा करते हैं जो एक गलत टाइप की तरह दिखता है।

पी.पी.एस. यह सीपीथॉन के लिए सच है, pypy different story है।