[Powered by Google Translate] तुम्हें शायद सुना है लोग एक तेज या कुशल एल्गोरिथ्म के बारे में बात करते हैं अपने विशेष कार्य निष्पादित करने के लिए, लेकिन क्या वास्तव में यह एक तेज या कुशल होना एल्गोरिथ्म के लिए क्या मतलब है? खैर, यह वास्तविक समय में एक माप के बारे में बात नहीं कर रहा है, सेकंड या मिनट की तरह. इसका कारण यह है कंप्यूटर हार्डवेयर और सॉफ्टवेयर काफी भिन्नता है. मेरा कार्यक्रम तुम्हारा की तुलना में धीमी चला सकता है, क्योंकि मैं इसे एक पुराने कंप्यूटर पर चल रहा है, या क्योंकि मैं एक ऑनलाइन वीडियो गेम खेल सकता हो एक ही समय में है, जो अपने सभी स्मृति hogging है, या मैं अलग सॉफ्टवेयर के माध्यम से मेरे प्रोग्राम चल रहा हो सकता है जो मशीन के साथ अलग संचार एक कम स्तर पर. यह सेब और संतरे की तुलना की तरह है. सिर्फ इसलिए कि मेरी धीमी कंप्यूटर अब लेता है से तुम्हारा वापस एक जवाब देने के लिए मतलब नहीं है कि आप और अधिक कुशल एल्गोरिथ्म है. 

तो, के बाद से हम सीधे कार्यक्रमों की runtimes नहीं की तुलना कर सकते हैं सेकंड या मिनट में, हम 2 अलग एल्गोरिदम कैसे तुलना करते हैं उनके हार्डवेयर या सॉफ्टवेयर पर्यावरण की परवाह किए बिना? एल्गोरिथम दक्षता को मापने का एक और अधिक समान तरीके से बनाने के लिए, कंप्यूटर वैज्ञानिकों और गणितज्ञों तैयार कर लिया है एक कार्यक्रम के asymptotic जटिलता को मापने के लिए अवधारणाओं और एक संकेतन 'बिग Ohnotation' कहा जाता है इस का वर्णन करने के लिए. औपचारिक परिभाषा यह है कि एक समारोह च (x) (x) जी के आदेश पर चलाता है अगर वहाँ कुछ मूल्य (x) मौजूद है, x ₀ और कुछ स्थिर, सी, जिसके लिए च (x) कम से कम या बराबर है कि लगातार कई बार जी (x) सभी x ₀ से अधिक एक्स के लिए. 

लेकिन औपचारिक परिभाषा से दूर डर नहीं सकता है. क्या यह वास्तव में कम सैद्धांतिक संदर्भ में क्या मतलब है? खैर, यह मूल रूप से विश्लेषण का एक तरीका है कितनी तेजी से एक कार्यक्रम के क्रम asymptotically बढ़ता है. यही कारण है, के रूप में अपने आदानों की आकार अनंत की ओर बढ़ता है, कहते हैं, आप 10 आकार की एक सरणी की तुलना में 1000 आकार की एक सरणी छँटाई कर रहे हैं. अपने कार्यक्रम के क्रम कैसे विकसित करता है? उदाहरण के लिए, वर्णों की संख्या गिनती की कल्पना एक स्ट्रिंग में सबसे सरल तरीका है  पूरे तार के माध्यम से चलने से पत्र द्वारा पत्र और हर किरदार के लिए एक काउंटर 1 जोड़ने. इस एल्गोरिथ्म रैखिक समय में चलाने के लिए कहा जाता है वर्णों की संख्या के संबंध में के साथ, 'एन' स्ट्रिंग में. संक्षेप में, यह O (n) में चलाता है. ऐसा क्यों है? खैर, इस दृष्टिकोण का उपयोग, समय की आवश्यकता पूरे स्ट्रिंग पार वर्णों की संख्या के लिए आनुपातिक है. 20-चरित्र एक स्ट्रिंग में वर्णों की संख्या गिनती करने के लिए दो बार के रूप में लंबे समय के रूप लेने के रूप में इसे लेता जा रहा है 10-चरित्र एक स्ट्रिंग में वर्ण गिनती, क्योंकि आप सभी पात्रों को देखने के लिए है और प्रत्येक वर्ण को देखने के समय का एक ही राशि लेता है. जैसा कि आप वर्णों की संख्या को बढ़ाने के लिए, क्रम linearly इनपुट लंबाई के साथ वृद्धि होगी. 

अब, कल्पना अगर आपको लगता है कि रैखिक समय तय है, हे (एन), बस तेजी से आप के लिए पर्याप्त नहीं था? शायद तुम भारी तार भंडारण कर रहे हैं, और आप अतिरिक्त समय ले जाएगा बर्दाश्त नहीं कर सकता उनके एक के बाद एक गिनती वर्णों की सभी पार. तो, आप कुछ अलग करने की कोशिश करने का फैसला. क्या होगा अगर आप पहले से ही वर्णों की संख्या की दुकान क्या होगा स्ट्रिंग में एक चर बुलाया में कहते हैं, 'लेन' जल्दी पर इस कार्यक्रम में, इससे पहले कि आप भी अपने स्ट्रिंग में बहुत पहले चरित्र संग्रहीत? तो, तुम सब स्ट्रिंग की लंबाई का पता लगाने के लिए अब क्या करना चाहते हैं, चर के मूल्य की जांच क्या है. आप ही सभी स्ट्रिंग को देखने के लिए नहीं होता, और लेन तरह एक चर के मूल्य तक पहुँचने माना जाता है एक asymptotically निरंतर समय आपरेशन, या हे (1). ऐसा क्यों है? अच्छी तरह याद है, asymptotic जटिलता का मतलब क्या है. आकार के रूप में क्रम परिवर्तन कैसे करता है अपने निविष्टियाँ बढ़ता है? 

कहते हैं कि तुम एक बड़ी स्ट्रिंग में वर्णों की संख्या पाने के लिए कोशिश कर रहे थे. खैर, यह बात नहीं करेंगे आप कितना बड़ा स्ट्रिंग बनाने, भी एक लाख वर्ण लंबा, आप इस दृष्टिकोण के साथ स्ट्रिंग लंबाई मिल करना होगा, चर लेन का मूल्य पढ़ा है, जो आप पहले से ही बनाया है. इनपुट लंबाई, वह यह है कि स्ट्रिंग की लंबाई आप खोजने की कोशिश कर रहे हैं, कितनी तेजी से अपने कार्यक्रम चलाता को प्रभावित नहीं करता है. अपने कार्यक्रम के इस हिस्से समान रूप से तेजी से एक स्ट्रिंग एक चरित्र पर चला जाएगा और एक हजार चरित्र स्ट्रिंग और यही कारण है कि इस कार्यक्रम को निरंतर समय में चल रहा है के रूप में संदर्भित किया जाएगा इनपुट आकार के लिए सम्मान के साथ. 

बेशक, वहाँ एक खामी है. आप अपने कंप्यूटर पर अतिरिक्त स्मृति अंतरिक्ष खर्च चर भंडारण के और अतिरिक्त समय यह आपको लगता है चर के वास्तविक भंडारण करते हैं, लेकिन बात अभी भी खड़ा है, बाहर लग रहा है कब तक अपने स्ट्रिंग थी स्ट्रिंग की लंबाई पर निर्भर नहीं करता है. इसलिए, यह हे (1) या निरंतर समय में चलाता है. यह निश्चित रूप से मतलब नहीं है कि अपने कोड चरण 1 में चलाता है, लेकिन कोई फर्क नहीं पड़ता कि कितने कदम यह है, अगर यह आदानों के आकार के साथ बदल नहीं है, यह अभी भी asymptotically निरंतर है जो हम हे (1) के रूप में प्रतिनिधित्व है. 

जैसा कि आप शायद अनुमान कर सकते हैं, वहाँ कई अलग अलग बड़ी हे साथ एल्गोरिदम को मापने runtimes हैं. हे (एन) ² एल्गोरिदम asymptotically हे एल्गोरिदम (एन) की तुलना में धीमी है. यही कारण है, के रूप में तत्वों की संख्या (n) बढ़ता है, अंततः हे (एन) ² एल्गोरिदम अधिक समय लगेगा हे एल्गोरिदम (एन) से चलाने के लिए. इसका मतलब यह नहीं है कि हे एल्गोरिदम (n) हमेशा तेजी से चलाने हे (एन) ² एल्गोरिदम से, यहां तक ​​कि एक ही वातावरण में, एक ही हार्डवेयर पर. शायद छोटे इनपुट आकार के लिए,  हे (एन) ² एल्गोरिथ्म वास्तव में तेजी से काम कर सकते हैं, लेकिन, अंत में, इनपुट आकार के रूप में बढ़ जाती है अनंत की ओर, हे (एन) ² एल्गोरिथ्म क्रम अंततः हे एल्गोरिथ्म (एन) के क्रम ग्रहण करेंगे. बस किसी भी द्विघात गणितीय समारोह की तरह  अंततः किसी भी रैखिक समारोह से आगे निकल जाएगा, कोई फर्क नहीं पड़ता कि कितना एक सिर के रैखिक समारोह शुरू के साथ शुरू होता है. यदि आप डेटा की बड़ी मात्रा के साथ काम कर रहे हैं, एल्गोरिदम कि हे में चलाने (एन) ² समय वास्तव में अंत में अपने कार्यक्रम धीमा कर सकते हैं, लेकिन छोटे इनपुट आकार के लिए, शायद आप भी नोटिस नहीं होगा. 

एक अन्य asymptotic जटिलता है, लघुगणक समय, हे (लॉग एन). एक एल्गोरिथ्म है कि यह जल्दी रन का एक उदाहरण क्लासिक द्विआधारी खोज एल्गोरिथ्म है, तत्वों की एक सूची में पहले से ही हल एक तत्व को खोजने के लिए. 

यदि आप नहीं जानते कि क्या द्विआधारी खोज करता है, मैं यह आप के लिए वास्तव में जल्दी से समझाता हूँ. मान लीजिए कि आप नंबर 3 के लिए देख रहे हैं पूर्णांकों की सरणी में. यह सरणी के बीच तत्व पर दिखता है और पूछता है, "तत्व मैं से अधिक चाहते हैं, बराबर करने के लिए, या कम से कम है?" अगर यह बराबर है, तो अच्छा है. आप तत्व पाया गया है, और आप कर रहे हैं. यदि यह अधिक से अधिक है, तो आप तत्व पता सरणी के सही पक्ष में हो गया है, और आप केवल भविष्य में उस पर विचार कर सकते हैं, और अगर यह छोटी है, तो आप जानते हैं कि यह बाईं ओर हो गया है. इस प्रक्रिया को फिर से छोटे आकार सरणी के साथ दोहराया है जब तक सही तत्व पाया जाता है. 

इस शक्तिशाली एल्गोरिथ्म छमाही में प्रत्येक आपरेशन के साथ सरणी आकार में कटौती. तो, 8 आकार का एक हल सरणी में एक तत्व को खोजने के लिए, सबसे अधिक है, (8 ₂ लॉग इन) या इन आपरेशनों के 3, मध्य तत्व जाँच कर रहा है, तो आधे में सरणी काटने की आवश्यकता होगी, जबकि 16 आकार की एक सरणी लेता है (लॉग इन 16 ₂), या 4 आपरेशनों. वह केवल 1 एक सरणी दोगुनी आकार के लिए अधिक आपरेशन है. सरणी के आकार दोहरीकरण इस कोड के केवल 1 हिस्सा द्वारा क्रम बढ़ जाती है. फिर, सूची के बीच तत्व की जाँच, तो बंटवारे. इसलिए, यह logarithmic समय में काम करने के लिए कहा गया है, हे (लॉग एन). लेकिन आप कहते हैं, रुको, करता है पर निर्भर नहीं करता, जहां इस सूची में तत्व आप के लिए देख रहे हैं? क्या होगा अगर पहली तत्व अपने आप को देखो एक सही करने के लिए होता है? फिर, यह केवल 1 आपरेशन लेता है, कोई फर्क नहीं पड़ता कि कैसे बड़ी सूची है. 

ठीक है, यही कारण है कि कंप्यूटर वैज्ञानिकों अधिक पदों asymptotic जटिलता जो सबसे अच्छा मामले को प्रतिबिंबित करने के लिए और सबसे ज्यादा मामले एक एल्गोरिथ्म के प्रदर्शन. ठीक है, ऊपरी और निचले सीमा क्रम पर. द्विआधारी खोज के लिए सबसे अच्छा मामले में, हमारे तत्व है सही बीच में, और आप इसे निरंतर समय में मिलता है, कोई फर्क नहीं पड़ता कि कितना बड़ा सरणी के बाकी है. इस के लिए इस्तेमाल किया प्रतीक Ω है. तो, इस एल्गोरिथ्म Ω (1) में चलाने के लिए कहा जाता है. सबसे अच्छी स्थिति में है, यह तत्व जल्दी पाता है, कोई फर्क नहीं पड़ता कि कितना बड़ा सरणी है, लेकिन सबसे खराब स्थिति में, यह (लॉग एन) विभाजन की जांच करने के सरणी के सही तत्व को खोजने के लिए. सबसे ज्यादा मामले ऊपरी सीमा को बड़ा "ओ" है कि आप पहले से ही पता है के साथ भेजा जाता है. इसलिए, यह हे (लॉग एन), लेकिन Ω (1) है. 

एक रैखिक खोज, इसके विपरीत, जिसमें आप सरणी के प्रत्येक तत्व के माध्यम से चलना एक आप करना चाहते हैं, Ω (1) में है. फिर, 1 तत्व आप चाहते हैं. इसलिए, यह कोई फर्क नहीं पड़ता कि कितना बड़ा सरणी है. सबसे खराब स्थिति में, यह सरणी में अंतिम तत्व है. तो, तुम सरणी में सभी n तत्वों के माध्यम से चलने के लिए इसे खोजने के लिए है, जैसे अगर आप एक 3 के लिए देख रहे थे. इसलिए, यह हे समय (एन) में चलाता क्योंकि यह सरणी में तत्वों की संख्या के लिए आनुपातिक है. 

एक और उपयोग प्रतीक Θ है. यह एल्गोरिदम जहां सबसे अच्छा और सबसे खराब मामलों का वर्णन करने के लिए इस्तेमाल किया जा सकता है वही कर रहे हैं. यह स्ट्रिंग लंबाई एल्गोरिदम के बारे में हम पहले बात की थी में मामला है. यही है, अगर हम एक चर में पहले दुकान हम स्ट्रिंग की दुकान है और यह निरंतर समय में बाद में उपयोग करें. कोई फर्क नहीं पड़ता कि क्या संख्या है हम उस चर में भंडारण कर रहे हैं, हम इसे देखना होगा. सबसे अच्छी बात है, हम इसे देखो और स्ट्रिंग की लंबाई पाते हैं. Ω (1) या तो सबसे अच्छा मामले लगातार समय. सबसे खराब मामला है, हम इसे देखो और स्ट्रिंग की लंबाई. तो, हे (1) या सबसे खराब स्थिति में लगातार समय. तो, सबसे अच्छा मामले और सबसे खराब मामलों के बाद से ही कर रहे हैं, इस Θ समय (1) में चलाने के लिए कहा जा सकता है. 

सारांश में, हम कोड दक्षता के बारे में कारण के लिए अच्छे तरीके हैं वास्तविक दुनिया समय वे भाग ले के बारे में कुछ भी जानने के बिना, जो बाहर कारकों से प्रभावित होता है, भिन्न हार्डवेयर, सॉफ्टवेयर सहित, या अपने कोड की बारीकियों. इसके अलावा, यह हमें अच्छी तरह के कारण के बारे में क्या होगा जब आदानों का आकार बढ़ जाती है. 

यदि आप हे (एन) एल्गोरिथ्म ² में चल रहे हैं, या बुरा, एक हे (2 ⁿ) एल्गोरिथ्म एक सबसे तेजी से बढ़ रही प्रकार के आप वास्तव में मंदी नोटिस शुरू करेंगे जब आप डेटा की बड़ी मात्रा के साथ काम करना शुरू करते हैं. 

वह asymptotic जटिलता है. धन्यवाद.