एल्गोरिदम का विश्लेषण

From Vigyanwiki
दी गई क्रमित सूची में दी गई प्रविष्टि को देखने के लिए, द्विआधारी खोज एल्गोरिथ्म और रैखिक खोज एल्गोरिथम (जो ऑर्डरिंग पर ध्यान नहीं देता) दोनों का उपयोग किया जा सकता है। पूर्व और बाद वाले एल्गोरिदम के विश्लेषण से पता चलता है कि यह अधिक से अधिक लेता है log2 n और n आकार की सूची के लिए क्रमशः चरणों की जाँच करें n. आकार 33 की चित्रित उदाहरण सूची में, मोरिन की खोज में, आर्थर बाइनरी के साथ 5 और 28 कदम उठाता है (में दिखाया गया है) cyan) और रैखिक (magenta) क्रमशः खोजें।
एल्गोरिदम के विश्लेषण में आमतौर पर उपयोग किए जाने वाले कार्यों के ग्राफ़, संचालन की संख्या दिखाते हैं N बनाम इनपुट आकार n प्रत्येक समारोह के लिए

कंप्यूटर विज्ञान में, एल्गोरिदम का विश्लेषण एल्गोरिदम की कम्प्यूटेशनल जटिलता को खोजने की प्रक्रिया है - उन्हें निष्पादित करने के लिए आवश्यक समय, भंडारण या अन्य संसाधनों की मात्रा। आमतौर पर, इसमें एक फ़ंक्शन (गणित) का निर्धारण करना शामिल होता है जो एक एल्गोरिथ्म के इनपुट के आकार को उसके द्वारा उठाए जाने वाले कदमों की संख्या (इसकी समय जटिलता) या इसके द्वारा उपयोग किए जाने वाले भंडारण स्थानों की संख्या (इसकी अंतरिक्ष जटिलता) से संबंधित करता है। एक एल्गोरिदम कुशल कहा जाता है जब इस फ़ंक्शन के मान छोटे होते हैं, या इनपुट के आकार में वृद्धि की तुलना में धीरे-धीरे बढ़ते हैं। एक ही आकार के अलग-अलग इनपुट के कारण एल्गोरिथम का अलग व्यवहार हो सकता है, इसलिए सर्वोत्तम, सबसे खराब और औसत केस विवरण सभी व्यावहारिक रुचि के हो सकते हैं। जब अन्यथा निर्दिष्ट नहीं किया जाता है, तो एल्गोरिथ्म के प्रदर्शन का वर्णन करने वाला फ़ंक्शन आमतौर पर एक ऊपरी सीमा होती है, जो कि एल्गोरिथम के सबसे खराब स्थिति इनपुट से निर्धारित होती है।

एल्गोरिदम का शब्द विश्लेषण डोनाल्ड नुथ द्वारा गढ़ा गया था।[1] एल्गोरिथ्म विश्लेषण व्यापक कम्प्यूटेशनल जटिलता सिद्धांत का एक महत्वपूर्ण हिस्सा है, जो किसी भी एल्गोरिदम द्वारा आवश्यक संसाधनों के लिए सैद्धांतिक अनुमान प्रदान करता है जो किसी दिए गए कम्प्यूटेशनल समस्या को हल करता है। ये अनुमान एल्गोरिथम दक्षता के लिए खोज की उचित दिशाओं में अंतर्दृष्टि प्रदान करते हैं।

एल्गोरिदम के सैद्धांतिक विश्लेषण में उनकी जटिलता का आकलन असिम्प्टोटिक अर्थ में करना आम है, यानी मनमाने ढंग से बड़े इनपुट के लिए जटिलता फ़ंक्शन का अनुमान लगाना। इसके लिए बिग ओ नोटेशन, बिग-ओमेगा नोटेशन और बिग-थीटा संकेतन का उपयोग किया जाता है। उदाहरण के लिए, बाइनरी खोज को आकार के लघुगणक के समानुपाती कई चरणों में चलाने के लिए कहा जाता है n खोजी जा रही क्रमबद्ध सूची का, या में O(log n), लघुगणकीय समय में बोलचाल की भाषा में। आमतौर पर स्पर्शोन्मुख विश्लेषण अनुमानों का उपयोग किया जाता है क्योंकि एक ही एल्गोरिथ्म के विभिन्न कार्यान्वयन दक्षता में भिन्न हो सकते हैं। हालांकि किसी दिए गए एल्गोरिथम के किसी भी दो उचित कार्यान्वयन की क्षमता एक निरंतर गुणक कारक से संबंधित होती है जिसे एक छिपा हुआ स्थिरांक कहा जाता है।

दक्षता के सटीक (असिम्प्टोटिक नहीं) उपायों की कभी-कभी गणना की जा सकती है लेकिन उन्हें आमतौर पर एल्गोरिथम के विशेष कार्यान्वयन से संबंधित कुछ मान्यताओं की आवश्यकता होती है, जिन्हें गणना का मॉडल कहा जाता है। संगणना के एक मॉडल को अमूर्त मशीन के संदर्भ में परिभाषित किया जा सकता है, उदा। ट्यूरिंग मशीन, और/या यह मानकर कि कुछ ऑपरेशन यूनिट समय में निष्पादित किए जाते हैं। उदाहरण के लिए, यदि क्रमबद्ध सूची जिसमें हम बाइनरी खोज लागू करते हैं n तत्व, और हम गारंटी दे सकते हैं कि सूची में किसी तत्व का प्रत्येक लुकअप इकाई समय में किया जा सकता है, फिर अधिकतम log2(n) + 1 उत्तर देने के लिए समय इकाइयों की आवश्यकता होती है।


लागत मॉडल

समय दक्षता का अनुमान इस बात पर निर्भर करता है कि हम एक चरण के रूप में क्या परिभाषित करते हैं। विश्लेषण के लिए वास्तविक रन-टाइम के लिए उपयोगी रूप से अनुरूप होने के लिए, एक चरण को पूरा करने के लिए आवश्यक समय को एक स्थिरांक के ऊपर बाध्य होने की गारंटी दी जानी चाहिए। यहाँ सावधान रहना चाहिए; उदाहरण के लिए, कुछ विश्लेषण दो संख्याओं के जोड़ को एक चरण के रूप में गिनते हैं। यह धारणा कुछ संदर्भों में वारंट नहीं हो सकती है। उदाहरण के लिए, यदि गणना में शामिल संख्याएँ मनमाने ढंग से बड़ी हो सकती हैं, तो एक जोड़ के लिए आवश्यक समय को स्थिर नहीं माना जा सकता है।

दो लागत मॉडल आम तौर पर उपयोग किए जाते हैं:[2]Cite error: Closing </ref> missing for <ref> tag[3][4]

  • यूनिफ़ॉर्म कॉस्ट मॉडल, जिसे यूनिफ़ॉर्म-कॉस्ट मेजरमेंट (और इसी तरह की विविधताएं) भी कहा जाता है, इसमें शामिल संख्याओं के आकार की परवाह किए बिना, हर मशीन के संचालन के लिए एक स्थिर लागत प्रदान करता है।
  • लघुगणक लागत मॉडल, जिसे लघुगणक-लागत माप (और इसी तरह की विविधताएं) भी कहा जाता है, शामिल बिट्स की संख्या के अनुपात में प्रत्येक मशीन संचालन के लिए लागत निर्दिष्ट करता है

उत्तरार्द्ध उपयोग करने के लिए अधिक बोझिल है, इसलिए यह केवल तभी नियोजित होता है जब आवश्यक हो, उदाहरण के लिए मनमाना-परिशुद्धता अंकगणितीय एल्गोरिदम के विश्लेषण में, जैसे कि क्रिप्टोग्राफी में उपयोग किया जाता है।

एक महत्वपूर्ण बिंदु जिसे अक्सर अनदेखा किया जाता है वह यह है कि समस्याओं के लिए प्रकाशित निचली सीमाएं अक्सर गणना के मॉडल के लिए दी जाती हैं जो संचालन के सेट से अधिक प्रतिबंधित होती है जिसे आप अभ्यास में उपयोग कर सकते हैं और इसलिए ऐसे एल्गोरिदम हैं जो भोलेपन की तुलना में तेज़ हैं संभव सोचा।[5]


रन-टाइम विश्लेषण

रन-टाइम विश्लेषण एक सैद्धांतिक वर्गीकरण है जो एक कलन विधि के DTIME (या रन-टाइम या निष्पादन समय) में इसकी जानकारी के रूप में वृद्धि का अनुमान लगाता है और अनुमान लगाता है (आमतौर पर इसके रूप में दर्शाया जाता है) n) बढ़ती है। कंप्यूटर विज्ञान में रन-टाइम दक्षता बहुत रुचि का विषय है: एक कंप्यूटर प्रोग्राम को क्रियान्वित करने में सेकंड, घंटे या साल भी लग सकते हैं, यह इस बात पर निर्भर करता है कि यह किस एल्गोरिथम को लागू करता है। जबकि सॉफ्टवेयर प्रोफाइलिंग तकनीकों का उपयोग व्यवहार में एक एल्गोरिथम के रन-टाइम को मापने के लिए किया जा सकता है, वे असीम रूप से कई संभावित इनपुट के लिए समय डेटा प्रदान नहीं कर सकते हैं; उत्तरार्द्ध केवल रन-टाइम विश्लेषण के सैद्धांतिक तरीकों से प्राप्त किया जा सकता है।

अनुभवजन्य मेट्रिक्स की कमियां

चूंकि एल्गोरिदम प्लेटफ़ॉर्म-स्वतंत्र हैं (यानी किसी दिए गए एल्गोरिदम को मनमाने ढंग से ऑपरेटिंग सिस्टम चलाने वाले मनमाने ढंग से कंप्यूटर पर मनमाने ढंग से प्रोग्रामिंग भाषा में लागू किया जा सकता है), दिए गए सेट के तुलनात्मक प्रदर्शन को मापने के लिए एक अनुभवजन्य दृष्टिकोण का उपयोग करने के लिए अतिरिक्त महत्वपूर्ण कमियां हैं एल्गोरिदम।

एक उदाहरण के रूप में एक प्रोग्राम लें जो आकार n के संयोजन सूची (कंप्यूटिंग) में एक विशिष्ट प्रविष्टि को देखता है। मान लीजिए कि यह प्रोग्राम कंप्यूटर ए पर लागू किया गया था, एक अत्याधुनिक मशीन, एक रेखीय खोज एल्गोरिथ्म का उपयोग करके, और कंप्यूटर बी पर, एक बहुत धीमी मशीन, एक द्विआधारी खोज एल्गोरिथ्म का उपयोग करके। अपने-अपने प्रोग्राम चलाने वाले दो कंप्यूटरों पर बेंचमार्क (कंप्यूटिंग) कुछ इस तरह दिख सकता है:

n (list size) Computer A run-time
(in nanoseconds)
Computer B run-time
(in nanoseconds)
16 8 100,000
63 32 150,000
250 125 200,000
1,000 500 250,000

इन मेट्रिक्स के आधार पर, यह निष्कर्ष निकालना आसान होगा कि कंप्यूटर ए एक एल्गोरिदम चला रहा है जो कंप्यूटर बी की तुलना में दक्षता में कहीं बेहतर है। हालांकि, यदि इनपुट-सूची का आकार पर्याप्त संख्या में बढ़ाया जाता है, उस निष्कर्ष को नाटकीय रूप से त्रुटि के रूप में प्रदर्शित किया गया है:

n (list size) Computer A run-time
(in nanoseconds)
Computer B run-time
(in nanoseconds)
16 8 100,000
63 32 150,000
250 125 200,000
1,000 500 250,000
... ... ...
1,000,000 500,000 500,000
4,000,000 2,000,000 550,000
16,000,000 8,000,000 600,000
... ... ...
63,072 × 1012 31,536 × 1012 ns,
or 1 year
1,375,000 ns,
or 1.375 milliseconds

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

वृद्धि के क्रम

अनौपचारिक रूप से, एक एल्गोरिदम को एक निश्चित इनपुट आकार से परे एक फ़ंक्शन (गणित) के आदेश पर विकास दर प्रदर्शित करने के लिए कहा जा सकता है। n, कार्यक्रम f(n) बार एक सकारात्मक स्थिरांक उस एल्गोरिथम के रन-टाइम के लिए एक स्पर्शोन्मुख विश्लेषण प्रदान करता है। दूसरे शब्दों में, दिए गए इनपुट आकार के लिए n कुछ से बड़ा n0 और एक स्थिर c, उस एल्गोरिथम का रन-टाइम इससे बड़ा कभी नहीं होगा c × f(n). यह अवधारणा अक्सर बिग ओ नोटेशन का उपयोग करके व्यक्त की जाती है। उदाहरण के लिए, चूंकि सम्मिलन सॉर्ट का रन-टाइम द्विघात वृद्धि करता है क्योंकि इसका इनपुट आकार बढ़ता है, इंसर्शन सॉर्ट को ऑर्डर का कहा जा सकता है O(n2).

बिग ओ नोटेशन सर्वश्रेष्ठ, सबसे खराब और औसत मामले को व्यक्त करने का एक सुविधाजनक तरीका है। किसी दिए गए एल्गोरिथ्म के लिए सबसे खराब स्थिति, हालांकि इसका उपयोग औसत-केस को व्यक्त करने के लिए भी किया जा सकता है - उदाहरण के लिए, जल्दी से सुलझाएं के लिए सबसे खराब स्थिति है O(n2), लेकिन औसत-केस रन-टाइम है O(n log n).

विकास के अनुभवजन्य आदेश

रन-टाइम मानते हुए शक्ति नियम का पालन करता है, tkna, गुणांक a पाया जा सकता है [6] रन-टाइम के अनुभवजन्य मापन द्वारा {t1, t2} कुछ समस्या-आकार बिंदुओं पर {n1, n2}, और गणना t2/t1 = (n2/n1)a ताकि a = log(t2/t1)/log(n2/n1). दूसरे शब्दों में, यह कुछ आकार बिंदु पर रन-टाइम बनाम इनपुट आकार के लॉग-लॉग प्लॉट पर अनुभवजन्य रेखा के ढलान को मापता है। यदि विकास का क्रम वास्तव में शक्ति नियम का पालन करता है (और इसलिए लॉग-लॉग प्लॉट पर रेखा वास्तव में एक सीधी रेखा है), का अनुभवजन्य मूल्य विभिन्न श्रेणियों पर स्थिर रहेगा, और यदि नहीं, तो यह बदल जाएगा (और रेखा एक घुमावदार रेखा है) - लेकिन फिर भी विकास व्यवहार के उनके अनुभवजन्य स्थानीय आदेशों के रूप में किसी भी दो एल्गोरिदम की तुलना करने के लिए काम कर सकता है। उपरोक्त तालिका पर लागू:

n (list size) Computer A run-time
(in nanoseconds)
Local order of growth
(n^_)
Computer B run-time
(in nanoseconds)
Local order of growth
(n^_)
15 7 100,000
65 32 1.04 150,000 0.28
250 125 1.01 200,000 0.21
1,000 500 1.00 250,000 0.16
... ... ...
1,000,000 500,000 1.00 500,000 0.10
4,000,000 2,000,000 1.00 550,000 0.07
16,000,000 8,000,000 1.00 600,000 0.06
... ... ...

यह स्पष्ट रूप से देखा गया है कि पहला एल्गोरिथ्म वास्तव में शक्ति नियम का पालन करते हुए विकास के एक रेखीय क्रम को प्रदर्शित करता है। दूसरे के लिए अनुभवजन्य मूल्य तेजी से कम हो रहे हैं, यह सुझाव दे रहा है कि यह विकास के एक और नियम का पालन करता है और किसी भी मामले में पहले की तुलना में विकास के स्थानीय क्रम (और अभी भी सुधार) बहुत कम है।

रन-टाइम जटिलता का मूल्यांकन

किसी दिए गए एल्गोरिदम के सबसे खराब स्थिति परिदृश्य के लिए रन-टाइम जटिलता का मूल्यांकन कभी-कभी एल्गोरिदम की संरचना की जांच करके और कुछ सरल अनुमानों को बनाकर किया जा सकता है। निम्नलिखित स्यूडोकोड पर विचार करें:

1 इनपुट से धनात्मक पूर्णांक n प्राप्त करें
2 'अगर' एन> 10
3 'प्रिंट' इसमें कुछ समय लग सकता है...
4 'के लिए' मैं = 1 'से' एन
5 'के लिए' जे = 1 'से' मैं
6 'प्रिंट' आई * जे
7 'प्रिंट' हो गया!

इस एल्गोरिथम को पूरा करने में शामिल प्रत्येक निर्देश (कंप्यूटर विज्ञान) को निष्पादित करने के लिए एक दिया गया कंप्यूटर एक DTIME लेगा। किसी दिए गए निर्देश को पूरा करने के लिए विशिष्ट समय अलग-अलग होगा, इस पर निर्भर करता है कि कौन सा निर्देश निष्पादित किया जा रहा है और कौन सा कंप्यूटर इसे निष्पादित कर रहा है, लेकिन एक पारंपरिक कंप्यूटर पर, यह राशि नियतात्मक प्रणाली (गणित) होगी।[7] कहें कि चरण 1 में किए गए कार्यों को समय टी का उपभोग करने के लिए माना जाता है1, चरण 2 समय T का उपयोग करता है2, इत्यादि।

उपरोक्त एल्गोरिद्म में, चरण 1, 2 और 7 केवल एक बार चलाए जाएंगे। सबसे खराब स्थिति के मूल्यांकन के लिए, यह माना जाना चाहिए कि चरण 3 भी चलाया जाएगा। इस प्रकार चरण 1-3 और चरण 7 को चलाने के लिए कुल समय है:

चरण 4, 5 और 6 में प्रोग्राम लूप का मूल्यांकन करना कठिन है। चरण 4 में बाहरी पाश परीक्षण निष्पादित होगा (n + 1) टाइम्स (ध्यान दें कि लूप को समाप्त करने के लिए एक अतिरिक्त चरण की आवश्यकता है, इसलिए n + 1 और n निष्पादन नहीं), जो T का उपभोग करेगा4(एन + 1) समय। दूसरी ओर, आंतरिक पाश, j के मान द्वारा शासित होता है, जो 1 से i तक चलता है। बाहरी लूप के पहले पास पर, j 1 से 1 तक दोहराता है: आंतरिक लूप एक पास बनाता है, इसलिए आंतरिक लूप बॉडी (चरण 6) को चलाने से T की खपत होती है6 समय, और इनर लूप टेस्ट (चरण 5) 2T की खपत करता है5 समय। बाहरी लूप के माध्यम से अगले पास के दौरान, j 1 से 2 तक पुनरावृत्त होता है: आंतरिक लूप दो पास बनाता है, इसलिए आंतरिक लूप बॉडी (चरण 6) को चलाने से 2T की खपत होती है6 समय, और इनर लूप टेस्ट (चरण 5) में 3T की खपत होती है5 समय।

कुल मिलाकर, आंतरिक लूप बॉडी को चलाने के लिए आवश्यक कुल समय अंकगणितीय प्रगति के रूप में व्यक्त किया जा सकता है:

जो गुणनखंड हो सकता है[8] जैसा

बाहरी पाश परीक्षण चलाने के लिए आवश्यक कुल समय का मूल्यांकन इसी प्रकार किया जा सकता है:

जिसे इस रूप में गिना जा सकता है

इसलिए, इस एल्गोरिथम के लिए कुल रन-टाइम है:

जो कम हो जाता है

अंगूठे के नियम के रूप में, कोई यह मान सकता है कि किसी दिए गए फ़ंक्शन में उच्चतम क्रम का शब्द विकास की दर पर हावी है और इस प्रकार इसके रन-टाइम ऑर्डर को परिभाषित करता है। इस उदाहरण में, एन2 उच्चतम क्रम वाला शब्द है, इसलिए कोई यह निष्कर्ष निकाल सकता है f(n) = O(n2). औपचारिक रूप से इसे इस प्रकार सिद्ध किया जा सकता है:

Prove that





Let k be a constant greater than or equal to [T1..T7]



Therefore

इस एल्गोरिदम का विश्लेषण करने के लिए एक और लालित्य दृष्टिकोण यह घोषित करना होगा कि [टी1..टी7] चुनी गई इकाइयों की प्रणाली में सभी समय की एक इकाई के बराबर हैं ताकि इन चरणों के लिए एक इकाई वास्तविक समय से अधिक या उसके बराबर हो। इसका मतलब यह होगा कि एल्गोरिथम का रन-टाइम निम्नानुसार टूट जाता है:[9]


अन्य संसाधनों का विकास दर विश्लेषण

रन-टाइम विश्लेषण की पद्धति का उपयोग अन्य विकास दरों, जैसे डीएसपीएसीई की खपत की भविष्यवाणी के लिए भी किया जा सकता है। एक उदाहरण के रूप में, निम्नलिखित स्यूडोकोड पर विचार करें जो प्रोग्राम द्वारा प्रबंधित कम्प्यूटर फाइल के आकार के आधार पर प्रोग्राम द्वारा मेमोरी उपयोग को प्रबंधित और पुन: आवंटित करता है:

जबकि फ़ाइल अभी भी खुली है:
    चलो n = फ़ाइल का आकार
    फ़ाइल आकार में वृद्धि के प्रत्येक 100,000 किलोबाइट के लिए
        आरक्षित स्मृति की दुगुनी मात्रा

इस उदाहरण में, जैसे ही फ़ाइल का आकार n बढ़ता है, स्मृति एक घातीय वृद्धि दर पर उपभोग की जाएगी, जो क्रम है O(2n). यह स्मृति संसाधन (कंप्यूटर विज्ञान) की खपत के लिए एक अत्यंत तीव्र और सबसे अधिक संभावना असहनीय विकास दर है।

प्रासंगिकता

एल्गोरिथम विश्लेषण व्यवहार में महत्वपूर्ण है क्योंकि एक अकुशल एल्गोरिथम का आकस्मिक या अनजाने में उपयोग सिस्टम के प्रदर्शन को महत्वपूर्ण रूप से प्रभावित कर सकता है। समय-संवेदी अनुप्रयोगों में, चलने में बहुत अधिक समय लेने वाला एल्गोरिद्म इसके परिणामों को पुराना या अनुपयोगी बना सकता है। एक अकुशल एल्गोरिथम को चलाने के लिए कंप्यूटिंग शक्ति या भंडारण की एक गैर-किफायती राशि की आवश्यकता भी समाप्त हो सकती है, फिर से इसे व्यावहारिक रूप से बेकार कर सकती है।

निरंतर कारक

एल्गोरिदम का विश्लेषण आम तौर पर स्पर्शोन्मुख प्रदर्शन पर ध्यान केंद्रित करता है, विशेष रूप से प्राथमिक स्तर पर, लेकिन व्यावहारिक अनुप्रयोगों में निरंतर कारक महत्वपूर्ण होते हैं, और वास्तविक दुनिया का डेटा व्यवहार में हमेशा आकार में सीमित होता है। सीमा आमतौर पर एड्रेसेबल मेमोरी के आकार की होती है, इसलिए 32-बिट मशीनों पर 232 = 4 GiB (यदि खंडित मेमोरी का उपयोग किया जाता है तो अधिक) और 64-बिट मशीनों पर 264 = 16 ईआईबी। इस प्रकार एक सीमित आकार दिया गया है, विकास का क्रम (समय या स्थान) एक स्थिर कारक द्वारा प्रतिस्थापित किया जा सकता है, और इस अर्थ में सभी व्यावहारिक एल्गोरिदम हैं O(1) पर्याप्त बड़े स्थिरांक के लिए, या पर्याप्त छोटे डेटा के लिए।

यह व्याख्या उन कार्यों के लिए मुख्य रूप से उपयोगी है जो बेहद धीमी गति से बढ़ते हैं: (बाइनरी) पुनरावृत्त लघुगणक (log*) सभी व्यावहारिक डेटा के लिए 5 से कम है (265536 बिट्स); (बाइनरी) लॉग-लॉग (लॉग लॉग एन) वस्तुतः सभी व्यावहारिक डेटा के लिए 6 से कम है (264 बिट्स); और वस्तुतः सभी व्यावहारिक डेटा के लिए बाइनरी लॉग (लॉग एन) 64 से कम है (264 बिट्स)। गैर-निरंतर जटिलता वाला एक एल्गोरिथम फिर भी व्यावहारिक डेटा पर निरंतर जटिलता वाले एल्गोरिथम की तुलना में अधिक कुशल हो सकता है यदि निरंतर समय एल्गोरिथम के ओवरहेड के परिणामस्वरूप एक बड़ा स्थिर कारक होता है, उदाहरण के लिए, एक हो सकता है जब तक और .

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

यह भी देखें

टिप्पणियाँ

  1. "Knuth: Recent News". 28 August 2016. Archived from the original on 28 August 2016.
  2. Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). The design and analysis of computer algorithms. Addison-Wesley Pub. Co. ISBN 9780201000290., section 1.3
  3. Wegener, Ingo (2005), Complexity theory: exploring the limits of efficient algorithms, Berlin, New York: Springer-Verlag, p. 20, ISBN 978-3-540-21045-0
  4. Robert Endre Tarjan (1983). Data structures and network algorithms. SIAM. pp. 3–7. ISBN 978-0-89871-187-5.
  5. Examples of the price of abstraction?, cstheory.stackexchange.com
  6. How To Avoid O-Abuse and Bribes Archived 2017-03-08 at the Wayback Machine, at the blog "Gödel's Lost Letter and P=NP" by R. J. Lipton, professor of Computer Science at Georgia Tech, recounting idea by Robert Sedgewick
  7. However, this is not the case with a quantum computer
  8. It can be proven by induction that
  9. This approach, unlike the above approach, neglects the constant time consumed by the loop tests which terminate their respective loops, but it is trivial to prove that such omission does not affect the final result


संदर्भ


बाहरी संबंध