सूची स्लाइसिंग के बिग-ओ

Question

कहें कि मेरे पास कुछ पायथन सूची है, my_list जिसमें एन तत्व शामिल हैं। my_list[i_1] का उपयोग कर एकल तत्वों को अनुक्रमित किया जा सकता है, जहां i_1 वांछित तत्व की अनुक्रमणिका है। हालांकि, पायथन सूची को my_list[i_1:i_2] अनुक्रमित किया जा सकता है, जहां i_1 से i_2 तक सूची का "टुकड़ा" वांछित है। आकार एन की सूची को टुकड़ा करने के लिए बिग-ओ (सबसे खराब मामला) नोटेशन क्या है?

व्यक्तिगत रूप से, अगर मैं "स्लाइसर" कोडिंग कर रहा था, तो मैं i_1 से i_2 से फिर से शुरू करूंगा, एक नई सूची उत्पन्न करूँगा और इसे वापस कर दूंगा, ओ (एन) का मतलब है, क्या यह पाइथन ऐसा करता है?

धन्यवाद,

Answer 1

एक टुकड़ा हो रही हे (i_2 - i_1) है। ऐसा इसलिए है क्योंकि एक सूची का पायथन का आंतरिक प्रतिनिधित्व एक सरणी है, इसलिए आप i_1 पर शुरू कर सकते हैं और i_2 पर फिर से शुरू कर सकते हैं।

अधिक जानकारी के लिए अजगर time complexity wiki entry

तुम भी CPython source में कार्यान्वयन देख सकते हैं यदि आप चाहते हैं देखते हैं।

Answer 2

आकार एन की सूची और आकार एम के टुकड़े के लिए, पुनरावृत्ति वास्तव में केवल ओ (एम) है, ओ (एन) नहीं। चूंकि एम अक्सर < < एन है, यह एक बड़ा अंतर बनाता है।

वास्तव में, यदि आप अपनी व्याख्या के बारे में सोचते हैं, तो आप देख सकते हैं क्यों। आप केवल i_1 से i_2 तक, 0 से i_1 तक, फिर I_1 से i_2 तक पुनरावृत्त कर रहे हैं।

Answer 3

http://wiki.python.org/moin/TimeComplexity

के अनुसार यह हे (के) जहां कश्मीर टुकड़ा आकार