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



python programming examples (3)

मुझे आश्चर्य है कि पायथन में सूची ऑब्जेक्ट्स की पॉप पद्धति की समय जटिलता (सीपीआईथॉन पार्ट्युलर में) क्या है। सूची पॉप (एन) के लिए एन का मूल्य भी जटिलता को प्रभावित करता है?


Answer #1

हाँ, यह ओ (1) एक पायथन सूची के आखिरी तत्व को पॉप करने के लिए है, और ओ (एन) एक मनमाना तत्व पॉप करने के लिए (चूंकि पूरी शेष सूची को स्थानांतरित किया जाना है)।

Python सूचियों को कैसे संग्रहीत और छेड़छाड़ किया गया है यह एक शानदार लेख है: http://effbot.org/zone/python-list.htm


Answer #2

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


Answer #3

संक्षिप्त उत्तर यहां दिखे : https://wiki.python.org/moin/TimeComplexity

इसके ओ पॉप करने के लिए कोई तर्क नहीं (1)

पॉप के तर्क के साथ:

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

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

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

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

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

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

  • 45 ओ (एनके) के बराबर है और जब से पॉप आपरेशन ओ (एन) का समय हो गया है, तो आपको एन (n)

Amortized सबसे खराब प्रकरण समय जटिलता

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

  • चूंकि सूची में 1 से गिरता है प्रत्येक बार कुल संचालन की संख्या हर बार 9 से 1 तक घट जाती है।

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

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

सबसे ज्यादा मामला समय जटिलता

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

अगर यह मदद करता है, तो इसके बारे में मुझे क्या लगता है:





python