पायथन में सूची से पॉपिंग तत्वों की समय जटिलता क्या है?

Question

मुझे आश्चर्य है कि पाइथन (सीपीथन कणिका में) सूची वस्तुओं की पॉप विधि की समय जटिलता क्या है। List.pop (एन) के लिए एन का मान भी जटिलता को प्रभावित करता है?

Answer 1

Pop() अंतिम तत्व के लिए ओ (1) होना चाहिए क्योंकि आपको केवल सरणी में अंतिम तत्व द्वारा संदर्भित तत्व को वापस करने और अंतिम तत्व की अनुक्रमणिका अद्यतन करने की आवश्यकता है। मैं उम्मीद करता हूं कि pop() एक मनमानी तत्व के लिए ओ (एन) होना चाहिए और औसत एन/2 संचालन की आवश्यकता है क्योंकि आपको उस तत्व से परे किसी भी तत्व को स्थानांतरित करने की आवश्यकता होगी जिसे आप पॉइंटर्स की सरणी में एक स्थिति को हटा रहे हैं।

Answer 2

हाँ, यह हे (1) पिछले एक अजगर सूची के तत्व पॉप है, और हे (एन) एक मनमाना तत्व पॉप (के बाद से सूची के पूरे आराम के लिए स्थानांतरित कर दिया जाना है)। http://effbot.org/zone/python-list.htm

Answer 3

संक्षिप्त उत्तर इधर देखो है:

यहाँ कैसे अजगर सूचियों संग्रहीत और छेड़छाड़ कर रहे हैं पर एक बड़ा लेख है https://wiki.python.org/moin/TimeComplexity

कोई तर्क के साथ

अपनी हे पॉप (1)

एक साथ

तर्क पॉप:

• औसत समय जटिलता हे (के) (के नंबर एक तर्क के रूप में पारित का प्रतिनिधित्व करता है पॉप के लिए
• परिशोधित सबसे खराब स्थिति समय जटिलता हे (के)
• सबसे खराब मामला समय जटिलता O (n)

औसत समय जटिलता:

• किसी भी समय आप एक में डाल उस ऑपरेशन की समय जटिलता मानें ओ (एन - के) है।

• उदाहरण के लिए, आप सूची के अंत से निकालने से 9 से मदों की एक सूची है, तो 9 संचालन और की शुरुआत से हटाने के सूची 1 परिचालन (0 सूचकांक को हटाने और अन्य सभी चलती है तत्वों को उनके वर्तमान सूचकांक में - 1)

• चूंकि सूची के मध्य तत्व के लिए एन-के के संचालन औसत है ओ (के) को औसत छोटा किया जा सकता है।

• इस बारे में सोचने का एक और तरीका यह है कि प्रत्येक इंडेक्स को आपकी 9 आइटम सूची से हटा दिया गया था। यह कुल 45 संचालन होगा। (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)

• 45 ओ (एनके) के बराबर है और चूंकि पॉप ऑपरेशन ओ (एन) बार हुआ जब आप एनके को एनके से विभाजित करते हैं हे (के) प्राप्त करने के लिए

परिशोधित सबसे खराब मामला समय जटिलता

• कल्पना कीजिए कि आप फिर से 9 मदों की एक सूची है।कल्पना करें कि आप सूची के हर आइटम को हटा रहे हैं और सबसे खराब मामला होता है और आप प्रत्येक बार सूची के पहले आइटम को हटा देते हैं।

• के बाद से सूची 1 से 1.

• 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 के माध्यम से हर बार की कुल संचालन की संख्या 9 से हर बार कम हो जाती है सिकुड़ता 45 बराबर ओ (एनके)। चूंकि आपने 9 ऑपरेशंस किए हैं और 9 एम (एन) को अमृतकृत सबसे खराब केस परिदृश्य की गणना करने के लिए ओ (एनके)/ओ (एन) है जो ओ (के)

• औसत के लिए ओ (एन) बताता है और अमूर्त खराब स्थिति समय जटिलता भी सही प्रकार का है। ध्यान दें कि हे (के) लगभग हे है (1/2n) और निरंतर गिर रहा हे के बराबर होती है (एन)

सबसे खराब मामला समय जटिलता

• परिशोधित सबसे खराब स्थिति समय जटिलता के साथ विपरीत आप डेटा संरचना की स्थिति में कारक मत बनो और किसी भी व्यक्तिगत ऑपरेशन के लिए सबसे खराब मामले के बारे में सोचें।
• उस उदाहरण में, सबसे खराब मामला आपको सूची से पहले आइटम को निकालना है जो ओ (एन) समय है।

Here's what I to think this through in case it helps: