समय जटिलता अजगर

Question

पढ़ना this question में बराबर हैं, मैंने सोचा कि कितना समय (asymptotically बोल) करता है ऐसा लगता है जैसे

{1,2}=={2,1} 

कि, कहने के लिए जाँच करने के लिए है भाव का मूल्यांकन करने के अजगर पर ले जाता है यदि set class के दो उदाहरण बराबर हैं।

Answer 1

सेट के बीच तुलना function set_richcompare in setobject.c, line 1848 द्वारा लागू की गई है। आप देखेंगे कि समानता लागू की गई है:

1. यदि सेट का आकार समान नहीं है, तो झूठी वापसी करें।

2. यदि दोनों सेट धोए गए हैं, और हैंश अलग हैं, तो झूठी वापसी करें।

3. कॉल set_issubset पर कॉल करें।

दो सेट के लिए सबसेट परीक्षण इस तरह दिखता है:

while (set_next(so, &pos, &entry)) { 
    int rv = set_contains_entry((PySetObject *)other, entry); 
    if (rv == -1) 
     return NULL; 
    if (!rv) 
     Py_RETURN_FALSE; 
} 
Py_RETURN_TRUE; 

आपको लगता है कि यह पहला सेट के सभी तत्वों से अधिक पुनरावृत्ति और फिर दूसरे में हर एक को देख कर काम करता है देखेंगे सेट। इसलिए (जब तक कि बहुत सारे हैश टकराव नहीं होते हैं) यह पहले सेट के आकार में रैखिक है।