अजगर

Question

मैं इस की चर्चा करते हुए कर रहा हूँ में list.index (एक्स) की जटिलता: http://docs.python.org/tutorial/datastructures.html

क्या बड़ा हे संकेतन के मामले में list.index(x) समारोह का चलने का समय हो सकता है?

Answer 1

यह हे (एन) है, यह भी देखें: http://wiki.python.org/moin/TimeComplexity

यह पृष्ठ वर्तमान CPython में विभिन्न कार्यों के समय जटिलता (उर्फ "बिग ओ" या "बिग ओह") दर्ज होते हैं। अन्य पायथन कार्यान्वयन (या सीपीथॉन के पुराने या अभी भी विकास संस्करणों के तहत) में थोड़ा अलग प्रदर्शन विशेषताएं हो सकती हैं। हालांकि, यह मान लेना कि वे हे (लॉग एन) का एक पहलू से भी अधिक से धीमी नहीं हैं आम तौर पर सुरक्षित है ...

Answer 2

के अनुसार कहा प्रलेखन:

list.index(x) 

वापसी सूचकांक पहले आइटम की सूची में जिसका मूल्य x है। यदि कोई ऐसी वस्तु नहीं है तो यह एक त्रुटि है।

जो खोज का तात्पर्य है। आप x in s प्रभावी ढंग से कर रहे हैं लेकिन True या False लौटने के बजाय आप x की अनुक्रमणिका लौट रहे हैं। इस प्रकार, मैं ओ (एन) के listed time complexity के साथ जाऊंगा।

Answer 3

किसी भी सूची कार्यान्वयन में एक रैखिक खोज (उदा।, List.index) के लिए ओ (एन) जटिलता होगी। यद्यपि वहां कुछ निराशाजनक कार्यान्वयन हैं जो बदतर हैं ...

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

जैसा कि पहले उल्लेख, यहाँ मानक पायथन डेटा संरचनाओं की रन टाइम लागत के लिए देखो: http://wiki.python.org/moin/TimeComplexity

Answer 4

इस कोड का प्रयास करें, यह मदद से आप अपने निष्पादन समय lis.index ऑपरेटर द्वारा लिए गए मिलता है।

import timeit 
lis=[11,22,33,44,55,66,77] 
for i in lis: 
    t = timeit.Timer("lis.index(11)", "from main import lis") 
    TimeTaken= t.timeit(number=100000) 
    print (TimeTaken)