स्मूथ्द एनालिसिस: Difference between revisions

Revision as of 10:59, 21 July 2023

बेतरतीब ढंग से उत्पन्न बिटमैप सामान्य चित्रों जैसा नहीं होता है।

एक सामान्य चित्र किसी रैंडम बिटमैप जैसा नहीं होता.

सैद्धांतिक कंप्यूटर विज्ञान में, स्मूथ्द एनालिसिस एल्गोरिदम के एनालिसिस को मापने की एक विधि है। 2001 में इसके प्रारंभ होने के बाद से, गणितीय प्रोग्रामिंग, नुमेरिकल एनालिसिस, मशीन लर्निंग और डेटा माइनिंग से लेकर समस्याओं के लिए स्मूथ्द एनालिसिस का उपयोग अधिक शोध के आधार के रूप में किया गया है।^[1] यह वर्स्ट केस या औसत-स्थिति परिदृश्यों का उपयोग करने वाले एनालिसिस की तुलना में एल्गोरिदम के व्यावहारिक प्रदर्शन (उदाहरण के लिए, रनिंग टाइम, सक्सेस रेट, अप्प्रोक्सिमेसन क्वालिटी) का अधिक यथार्थवादी एनालिसिस दे सकता है।

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

यद्यपि वर्स्ट केस एनालिसिस कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, एनालिसिस की यह शैली कई समस्याओं के लिए मिसलीडिंग परिणाम देती है। वर्स्ट केस कोम्प्लेक्ससिटी किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, चूँकि हल करने में कठिन इनपुट अभ्यास में कभी नहीं आ सकते हैं। ऐसे स्थितियों में, वर्स्ट केस रनिंग टाइम अभ्यास में ओब्सेर्वे रनिंग टाइम कहीं अधिक वोर्स हो सकता है। उदाहरण के लिए, सिम्प्लेक्स एल्गोरिथ्म का उपयोग करके एक लीनियर प्रोग्राम को हल करने की वर्स्ट केस कोम्प्लेक्ससिटी घातीय है,^[2] चूँकि अभ्यास में चरणों की देखी गई संख्या सामान्य रूप से लीनियर है।^[3]^[4] सिम्पलेक्स एल्गोरिथ्म वास्तव में अभ्यास में एल्लिप्सोइड विधि की तुलना में बहुत तेज़ है, चूँकि उत्तरार्द्ध में पालीनोमिअल टाइम की वर्स्ट केस वाली कोम्प्लेक्ससिटी है।

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

स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस दोनों को सामान्यीकृत करता है और दोनों की शक्ति प्राप्त करता है। इसका उद्देश्य औसत-स्थिति की कोम्प्लेक्ससिटी से कहीं अधिक सामान्य होना है जबकि अभी भी कम कोम्प्लेक्ससिटी सीमाओं को सिद्ध करने की अनुमति है।

इतिहास

एसीएम और ईएटीसीएस ने स्मूथ्द एनालिसिस विकसित करने के लिए डेनियल स्पीलमैन और शांग ड्रा टी को 2008 गोडेल प्राइज से सम्मानित किया था। स्मूथेड एनालिसिस नाम एलन एडेलमैन द्वारा डेवलपिंग किया गया था।^[1] 2010 में स्पीलमैन को स्मूथ्द एनालिसिस विकसित करने के लिए नेवानलिन्ना प्राइज मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का स्मूथ्द एनालिसिस: सिम्प्लेक्स एल्गोरिदम सामान्यत: बहुपद समय क्यों लेता है, गणितीय प्रोग्रामिंग सोसायटी (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन प्राइज के तीन विजेताओं में से एक था।

उदाहरण

लीनियर प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

सिम्प्लेक्स एल्गोरिदम अभ्यास में एक बहुत ही कुशल एल्गोरिदम है, और यह अभ्यास में लीनियर प्रोग्रामिंग के लिए प्रमुख एल्गोरिदम में से एक है। प्रायोगिक समस्याओं पर, एल्गोरिदम द्वारा उठाए गए कदमों की संख्या चर और बाधाओं की संख्या में लीनियर है।^[3]^[4] फिर भी सैद्धांतिक रूप से वर्स्ट केस में सबसे सफलतापूर्वक विश्लेषित धुरी नियमों के लिए इसमें तेजी से कई कदम उठाने पड़ते हैं। स्मूथ्द एनालिसिस विकसित करने के लिए यह मुख्य प्रेरणाओं में से एक था।^[5]

पेरटूरबाशन मॉडल के लिए, हम मानते हैं कि इनपुट डेटा गाऊसी डिस्ट्रीब्यूशन से ध्वनि से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं ${\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}$ संतुष्ट $\|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1$ सभी पंक्तियों के लिए $({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})$ आव्यूह का $({\bar {\mathbf {A} }},{\bar {\mathbf {b} }}).$ ये ध्वनि $({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})$ माध्य के साथ गाऊसी डिस्ट्रीबुसन से नमूना की गई स्वतंत्र प्रविष्टियाँ $0$ और मानक विचलन $\sigma$ . हमने $\mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}$ .सेट किया है जो स्मूथ्द इनपुट डेटा में लीनियर प्रोग्राम सम्मिलित होता है

अधिकतम करें

\mathbf {c^{T}} \cdot \mathbf {x}

का विषय है

\mathbf {A} \mathbf {x} \leq \mathbf {b}

.

यदि डेटा पर हमारे एल्गोरिदम का चलने का समय $\mathbf {A} ,\mathbf {b} ,\mathbf {c}$ द्वारा दिया गया है $T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )$ तो सिंप्लेक्स विधि की स्मूथ्द कोम्प्लेक्ससिटी है^[6]

C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).

यह सीमा एक विशिष्ट धुरी नियम के लिए है जिसे छाया शीर्ष नियम कहा जाता है। शैडो वर्टेक्स नियम सामान्यत: उपयोग किए जाने वाले धुरी नियमों जैसे कि डेंटज़िग नियम या सबसे तेज किनारे वाले नियम की तुलना में धीमा है^[7] किंतु इसमें ऐसे गुण हैं जो इसे संभाव्य एनालिसिस के लिए बहुत उपयुक्त बनाते हैं।^[8]

संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन

कई स्थानीय खोज (अनुकूलन) एल्गोरिदम का चलने का समय सबसे व्यर्थ होता है, किंतु अभ्यास में वे अच्छा प्रदर्शन करते हैं।^[9]

एक उदाहरण ट्रैवलिंग सेल्समैन की समस्या के लिए 2-ऑप्ट अनुमानी है। स्थानीय रूप से इष्टतम समाधान मिलने तक इसमें तेजी से कई पुनरावृत्तियां हो सकती हैं, चूँकि अभ्यास में चलने का समय वेर्टिसस की संख्या में सबक्वाड्रैटीक है।^[10] अप्प्रोक्सिमेसन रेश्यो, जो एल्गोरिदम के आउटपुट की लंबाई और इष्टतम समाधान की लंबाई के बीच का अनुपात है, अभ्यास में अच्छा होता है किंतु सैद्धांतिक रूप से वर्स्ट केस में भी व्यर्थ हो सकता है।

समस्या उदाहरणों का एक वर्ग बॉक्स $[0,1]^{d}$ में $n$ बिंदुओं द्वारा दिया जा सकता है, जहां उनकी जोड़ीदार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई पेरटूरबाशन मॉडल का विश्लेषण कर सकता है जहां कोने $v_{1},\dots ,v_{n}$ को प्रोबब्लिटी डेंसिटी फ़ंक्शन $f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]$ के साथ युनिफोर्मिली डिस्ट्रीबुसन के अनुसार स्वतंत्र रूप से नमूना किया जाता है। $\theta =1$ के लिए, अंक समान रूप से वितरित किए गए हैं। जब $\theta >1$ बड़ा होता है, तो प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस पेरटूरबाशन मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात, $n$ और $\theta$ के बहुपद कार्यों से बंधे हैं।^[10]

एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए स्मूथ्द एनालिसिस सफल रहा वह के-मीन्स विधि है। $[0,1]^{d}$ में $n$ अंक दिए जाने पर, एक ही क्लस्टर में बिंदुओं के बीच छोटी जोड़ीदार दूरी वाले समूहों में एक अच्छा विभाजन खोजना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और अभ्यास में बहुत तेज़ है, चूँकि यह स्थानीय रूप से इष्टतम समाधान खोजने के लिए सबसे वर्स्ट केस में पुनरावृत्तियों को ले सकता है। चूँकि यह मानते हुए कि बिंदुओं में स्वतंत्र गॉसियन डिस्ट्रीबुसन हैं, प्रत्येक की अपेक्षा $[0,1]^{d}$ और मानक विचलन $\sigma$ है, एल्गोरिदम के पुनरावृत्तियों की अपेक्षित संख्या $n$ , $d$ और $\sigma$ . में एक बहुपद से घिरी है।^[11]

यह भी देखें

एवरेज केस कॉम्पलेक्ससिटी
सूडो -पालीनोमिअल टाइम
वर्स्ट केस कॉम्पलेक्ससिटी

संदर्भ

↑ ^1.0 ^1.1 Spielman, Daniel; Teng, Shang-Hua (2009), "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF), Communications of the ACM, ACM, 52 (10): 76–84, doi:10.1145/1562764.1562785
↑ Amenta, Nina; Ziegler, Günter (1999), "Deformed products and maximal shadows of polytopes", Contemporary Mathematics, American Mathematical Society, 223: 10–19, CiteSeerX 10.1.1.80.3241, doi:10.1090/conm/223, ISBN 9780821806746, MR 1661377
↑ ^3.0 ^3.1 Shamir, Ron (1987), "The Efficiency of the Simplex Method: A Survey", Management Science, 33 (3): 301–334, doi:10.1287/mnsc.33.3.301
↑ ^4.0 ^4.1 Andrei, Neculai (2004), "Andrei, Neculai. "On the complexity of MINOS package for linear programming", Studies in Informatics and Control, 13 (1): 35–46
↑ Spielman, Daniel; Teng, Shang-Hua (2001), "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time", Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM: 296–305, arXiv:cs/0111050, Bibcode:2001cs.......11050S, doi:10.1145/380752.380813, ISBN 978-1-58113-349-3
↑ Dadush, Daniel; Huiberts, Sophie (2018), "A friendly smoothed analysis of the simplex method", Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing: 390–403, arXiv:1711.05667, doi:10.1145/3188745.3188826, ISBN 9781450355599
↑ Borgwardt, Karl-Heinz; Damm, Renate; Donig, Rudolf; Joas, Gabriele (1993), "Empirical studies on the average efficiency of simplex variants under rotation symmetry", ORSA Journal on Computing, Operations Research Society of America, 5 (3): 249–260, doi:10.1287/ijoc.5.3.249
↑ Borgwardt, Karl-Heinz (1987), The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, vol. 1, Springer-Verlag, doi:10.1007/978-3-642-61578-8, ISBN 978-3-540-17096-9
↑ Manthey, Bodo (2021), Roughgarden, Tim (ed.), "Smoothed Analysis of Local Search", Beyond the Worst-Case Analysis of Algorithms, Cambridge: Cambridge University Press, pp. 285–308, doi:10.1017/9781108637435.018, ISBN 978-1-108-49431-1, retrieved 2022-06-15
↑ ^10.0 ^10.1 Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2007), "Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 68: 190–264, doi:10.1007/s00453-013-9801-4
↑ Arthur, David; Manthey, Bodo; Röglin, Heiko (2011), "Smoothed Analysis of the k-Means Method", Journal of the ACM, 58 (5): 1–31, doi:10.1145/2027216.2027217

[spielman-teng-2009-1] 1.0 ^1.1 Spielman, Daniel; Teng, Shang-Hua (2009), "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF), Communications of the ACM, ACM, 52 (10): 76–84, doi:10.1145/1562764.1562785

[amenta-ziegler-2] Amenta, Nina; Ziegler, Günter (1999), "Deformed products and maximal shadows of polytopes", Contemporary Mathematics, American Mathematical Society, 223: 10–19, CiteSeerX 10.1.1.80.3241, doi:10.1090/conm/223, ISBN 9780821806746, MR 1661377

[shamir-3] 3.0 ^3.1 Shamir, Ron (1987), "The Efficiency of the Simplex Method: A Survey", Management Science, 33 (3): 301–334, doi:10.1287/mnsc.33.3.301

[andrei-4] 4.0 ^4.1 Andrei, Neculai (2004), "Andrei, Neculai. "On the complexity of MINOS package for linear programming", Studies in Informatics and Control, 13 (1): 35–46

[spielman-teng-2001-5] Spielman, Daniel; Teng, Shang-Hua (2001), "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time", Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM: 296–305, arXiv:cs/0111050, Bibcode:2001cs.......11050S, doi:10.1145/380752.380813, ISBN 978-1-58113-349-3

[6] Dadush, Daniel; Huiberts, Sophie (2018), "A friendly smoothed analysis of the simplex method", Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing: 390–403, arXiv:1711.05667, doi:10.1145/3188745.3188826, ISBN 9781450355599

[borgwardt-damm-donig-joas-7] Borgwardt, Karl-Heinz; Damm, Renate; Donig, Rudolf; Joas, Gabriele (1993), "Empirical studies on the average efficiency of simplex variants under rotation symmetry", ORSA Journal on Computing, Operations Research Society of America, 5 (3): 249–260, doi:10.1287/ijoc.5.3.249

[borgwardt-8] Borgwardt, Karl-Heinz (1987), The Simplex Method: A Probabilistic Analysis, Algorithms and Combinatorics, vol. 1, Springer-Verlag, doi:10.1007/978-3-642-61578-8, ISBN 978-3-540-17096-9

[9] Manthey, Bodo (2021), Roughgarden, Tim (ed.), "Smoothed Analysis of Local Search", Beyond the Worst-Case Analysis of Algorithms, Cambridge: Cambridge University Press, pp. 285–308, doi:10.1017/9781108637435.018, ISBN 978-1-108-49431-1, retrieved 2022-06-15

[engler-roeglin-voecking-10] 10.0 ^10.1 Englert, Matthias; Röglin, Heiko; Vöcking, Berthold (2007), "Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP", Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 68: 190–264, doi:10.1007/s00453-013-9801-4

[david-manthey-roeglin-11] Arthur, David; Manthey, Bodo; Röglin, Heiko (2011), "Smoothed Analysis of the k-Means Method", Journal of the ACM, 58 (5): 1–31, doi:10.1145/2027216.2027217

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

@@ Line 1: / Line 1: @@
 [[File:Every pixel has a random color.png|thumb|बेतरतीब ढंग से उत्पन्न [[बिटमैप]] सामान्य चित्रों जैसा नहीं होता है।]]
-[[File:Edible fungi in basket 2012 G1.jpg|thumb|एक सामान्य चित्र किसी यादृच्छिक बिटमैप जैसा नहीं होता.]][[सैद्धांतिक कंप्यूटर विज्ञान]] में, सुचारु विश्लेषण एल्गोरिदम के विश्लेषण को मापने का एक तरीका है। 2001 में इसकी शुरुआत के बाद से, [[गणितीय प्रोग्रामिंग]], [[संख्यात्मक विश्लेषण]], [[ यंत्र अधिगम ]] और [[डेटा खनन]] से लेकर समस्याओं के लिए सुचारु विश्लेषण का उपयोग काफी शोध के आधार के रूप में किया गया है।<ref name="spielman-teng-2009" />यह सबसे खराब स्थिति या औसत-मामले परिदृश्यों का उपयोग करने वाले विश्लेषण की तुलना में एल्गोरिदम के व्यावहारिक प्रदर्शन (उदाहरण के लिए, चलने का समय, सफलता दर, अनुमानित गुणवत्ता) का अधिक यथार्थवादी विश्लेषण दे सकता है।
+[[File:Edible fungi in basket 2012 G1.jpg|thumb|एक सामान्य चित्र किसी रैंडम बिटमैप जैसा नहीं होता.]][[सैद्धांतिक कंप्यूटर विज्ञान]] में, '''स्मूथ्द एनालिसिस''' एल्गोरिदम के एनालिसिस को मापने की एक विधि है। 2001 में इसके प्रारंभ होने के बाद से, [[गणितीय प्रोग्रामिंग]], [[संख्यात्मक विश्लेषण|नुमेरिकल एनालिसिस]], [[ यंत्र अधिगम | मशीन लर्निंग]] और [[डेटा खनन|डेटा माइनिंग]]  से लेकर समस्याओं के लिए स्मूथ्द एनालिसिस का उपयोग अधिक  शोध के आधार के रूप में किया गया है।<ref name="spielman-teng-2009" /> यह वर्स्ट केस या औसत-स्थिति परिदृश्यों का उपयोग करने वाले एनालिसिस की तुलना में एल्गोरिदम के व्यावहारिक प्रदर्शन (उदाहरण के लिए, रनिंग टाइम, सक्सेस रेट, अप्प्रोक्सिमेसन क्वालिटी) का अधिक यथार्थवादी एनालिसिस दे सकता है।
-सहज विश्लेषण सबसे खराब स्थिति और औसत-मामले विश्लेषण का एक मिश्रण है जो दोनों के फायदे प्राप्त करता है। यह सबसे खराब स्थिति वाले इनपुट के मामूली यादृच्छिक गड़बड़ी के तहत एल्गोरिदम के अपेक्षित प्रदर्शन को मापता है। यदि किसी एल्गोरिदम की सुचारु जटिलता कम है, तो यह संभावना नहीं है कि एल्गोरिदम को व्यावहारिक उदाहरणों को हल करने में लंबा समय लगेगा, जिनका डेटा मामूली शोर और अशुद्धियों के अधीन है। सुचारू जटिलता परिणाम मजबूत संभाव्य परिणाम हैं, मोटे तौर पर यह बताते हुए कि, इनपुट के स्थान के प्रत्येक बड़े पर्याप्त पड़ोस में, अधिकांश इनपुट आसानी से हल करने योग्य हैं। इस प्रकार, कम चिकनी जटिलता का मतलब है कि इनपुट की कठोरता एक भंगुर संपत्ति है।
+स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस का एक मिश्रण है जो दोनों के लाभ प्राप्त करता है। यह वर्स्ट केस वाले इनपुट के समान्य रैनडम पेरटूरबाशन  के तहत एल्गोरिदम के अपेक्षित प्रदर्शन को मापता है। यदि किसी एल्गोरिदम की स्मूथ्द कोम्प्लेक्ससिटी कम है, तो यह संभावना नहीं है कि एल्गोरिदम को व्यावहारिक उदाहरणों को हल करने में लंबा समय लगेगा, जिनका डेटा सामान्य ध्वनि और अशुद्धियों के अधीन है। स्मूथ्द कोम्प्लेक्ससिटी परिणाम शसक्त संभाव्य परिणाम हैं, सामान्य रूप से यह बताते हुए कि, इनपुट के स्थान के प्रत्येक बड़े पर्याप्त निकट में, अधिकांश इनपुट आसानी से हल करने योग्य हैं। इस प्रकार, लो स्मूथ्द कोम्प्लेक्ससिटी का अर्थ है कि इनपुट की कठोरता एक ब्रिटत्ल प्रॉपर्टी है।
-यद्यपि [[सबसे खराब स्थिति का विश्लेषण]] कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, विश्लेषण की यह शैली कई समस्याओं के लिए भ्रामक परिणाम देती है। सबसे खराब स्थिति की जटिलता किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, हालांकि हल करने में मुश्किल इनपुट व्यवहार में कभी नहीं आ सकते हैं। ऐसे मामलों में, सबसे खराब स्थिति में चलने का समय व्यवहार में देखे गए चलने के समय से कहीं अधिक खराब हो सकता है। उदाहरण के लिए, [[सिम्प्लेक्स एल्गोरिथ्म]] का उपयोग करके एक [[रैखिक कार्यक्रम]] को हल करने की सबसे खराब स्थिति जटिलता घातीय है,<ref name="amenta-ziegler" />हालाँकि व्यवहार में चरणों की देखी गई संख्या मोटे तौर पर रैखिक है।<ref name="shamir" /><ref name="andrei" />सिम्पलेक्स एल्गोरिथ्म वास्तव में व्यवहार में दीर्घवृत्ताकार विधि की तुलना में बहुत तेज़ है, हालांकि उत्तरार्द्ध में [[कमजोर बहुपद]]|बहुपद-समय की सबसे खराब स्थिति वाली जटिलता है।
+यद्यपि [[सबसे खराब स्थिति का विश्लेषण|वर्स्ट केस]] एनालिसिस कई एल्गोरिदम के व्यावहारिक प्रदर्शन को समझाने में व्यापक रूप से सफल रहा है, एनालिसिस की यह शैली कई समस्याओं के लिए मिसलीडिंग परिणाम देती है। [[सबसे खराब स्थिति का विश्लेषण|वर्स्ट केस]] कोम्प्लेक्ससिटी किसी भी इनपुट को हल करने में लगने वाले समय को मापती है, चूँकि  हल करने में कठिन इनपुट अभ्यास में कभी नहीं आ सकते हैं। ऐसे स्थितियों में, वर्स्ट केस रनिंग टाइम अभ्यास में ओब्सेर्वे रनिंग टाइम  कहीं अधिक वोर्स हो सकता है। उदाहरण के लिए, [[सिम्प्लेक्स एल्गोरिथ्म]] का उपयोग करके एक [[रैखिक कार्यक्रम|लीनियर प्रोग्राम]] को हल करने की वर्स्ट केस कोम्प्लेक्ससिटी घातीय है,<ref name="amenta-ziegler" /> चूँकि अभ्यास में चरणों की देखी गई संख्या सामान्य रूप से लीनियर है।<ref name="shamir" /><ref name="andrei" /> सिम्पलेक्स एल्गोरिथ्म वास्तव में अभ्यास में एल्लिप्सोइड विधि की तुलना में बहुत तेज़ है, चूँकि उत्तरार्द्ध में पालीनोमिअल टाइम  की वर्स्ट केस वाली कोम्प्लेक्ससिटी है।
-औसत-केस विश्लेषण सबसे पहले सबसे खराब-केस विश्लेषण की सीमाओं को दूर करने के लिए पेश किया गया था। हालाँकि, परिणामी औसत-मामले की जटिलता इनपुट पर चुने गए संभाव्यता वितरण पर बहुत अधिक निर्भर करती है। व्यवहार में वास्तविक इनपुट और इनपुट का वितरण विश्लेषण के दौरान बनाई गई धारणाओं से भिन्न हो सकता है: एक यादृच्छिक इनपुट एक विशिष्ट इनपुट से बहुत भिन्न हो सकता है। डेटा मॉडल की इस पसंद के कारण, सैद्धांतिक औसत-मामले का परिणाम एल्गोरिदम के व्यावहारिक प्रदर्शन के बारे में बहुत कम कह सकता है।
+औसत-केस एनालिसिस सबसे पहले सबसे वर्स्ट -केस एनालिसिस की सीमाओं को दूर करने के लिए प्रस्तुत  किया गया था। चूँकि, परिणामी औसत-स्थिति की कोम्प्लेक्ससिटी इनपुट पर चुने गए प्रोबब्लिटी डिस्ट्रीबुसन  पर बहुत अधिक निर्भर करती है। वास्तव में वास्तविक इनपुट और इनपुट का डिस्ट्रीबुसन एनालिसिस के समय बनाई गई धारणाओं से भिन्न हो सकता है: एक रैंडम इनपुट एक विशिष्ट इनपुट से बहुत भिन्न हो सकता है। डेटा मॉडल की इस पसंद के कारण, सैद्धांतिक औसत-स्थति का परिणाम एल्गोरिदम के व्यावहारिक प्रदर्शन के बारे में बहुत कम कह सकता है।
-सुचारू विश्लेषण सबसे खराब स्थिति और औसत-मामले विश्लेषण दोनों को सामान्यीकृत करता है और दोनों की ताकत प्राप्त करता है। इसका उद्देश्य औसत-मामले की जटिलता से कहीं अधिक सामान्य होना है, जबकि अभी भी कम जटिलता सीमाओं को सिद्ध करने की अनुमति है।
+स्मूथ्द एनालिसिस वर्स्ट केस और औसत-स्थिति एनालिसिस दोनों को सामान्यीकृत करता है और दोनों की शक्ति प्राप्त करता है। इसका उद्देश्य औसत-स्थिति की कोम्प्लेक्ससिटी से कहीं अधिक सामान्य होना है जबकि अभी भी कम कोम्प्लेक्ससिटी सीमाओं को सिद्ध करने की अनुमति है।
 ==इतिहास==
-[[संगणक तंत्र संस्था]] और [[ईएटीसीएस]] ने सुचारू विश्लेषण विकसित करने के लिए [[डेनियल स्पीलमैन]] और [[शांग ड्रा टी]] को 2008 गोडेल पुरस्कार से सम्मानित किया। स्मूथेड एनालिसिस नाम [[एलन एडेलमैन]] द्वारा गढ़ा गया था।<ref name="spielman-teng-2009" />2010 में स्पीलमैन को सुचारु विश्लेषण विकसित करने के लिए [[नेवानलिन्ना पुरस्कार]] मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का सहज विश्लेषण: सिम्प्लेक्स एल्गोरिदम आमतौर पर बहुपद समय क्यों लेता है, [[गणितीय प्रोग्रामिंग सोसायटी]] (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन पुरस्कार के तीन विजेताओं में से एक था।
+[[संगणक तंत्र संस्था|एसीएम]] और  [[ईएटीसीएस]] ने स्मूथ्द एनालिसिस विकसित करने के लिए [[डेनियल स्पीलमैन]] और [[शांग ड्रा टी]] को 2008 गोडेल प्राइज से सम्मानित किया था। स्मूथेड एनालिसिस नाम [[एलन एडेलमैन]] द्वारा डेवलपिंग किया गया था।<ref name="spielman-teng-2009" /> 2010 में स्पीलमैन को स्मूथ्द एनालिसिस विकसित करने के लिए [[नेवानलिन्ना पुरस्कार|नेवानलिन्ना प्राइज]] मिला। स्पीलमैन और टेंग का जेएसीएम पेपर एल्गोरिदम का स्मूथ्द एनालिसिस: सिम्प्लेक्स एल्गोरिदम सामान्यत: बहुपद समय क्यों लेता है, [[गणितीय प्रोग्रामिंग सोसायटी]] (एमपीएस) और अमेरिकन गणितीय सोसाइटी (एएमएस) द्वारा संयुक्त रूप से प्रायोजित 2009 फुलकर्सन प्राइज के तीन विजेताओं में से एक था।
 ==उदाहरण==
-===[[रैखिक प्रोग्रामिंग]] के लिए सिंप्लेक्स एल्गोरिदम===
+===[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]] के लिए सिंप्लेक्स एल्गोरिदम===
-सिम्प्लेक्स एल्गोरिदम व्यवहार में एक बहुत ही कुशल एल्गोरिदम है, और यह व्यवहार में रैखिक प्रोग्रामिंग के लिए प्रमुख एल्गोरिदम में से एक है। व्यावहारिक समस्याओं पर, एल्गोरिदम द्वारा उठाए गए कदमों की संख्या चर और बाधाओं की संख्या में रैखिक है।<ref name="shamir" /><ref name="andrei" />फिर भी सैद्धांतिक रूप से सबसे खराब स्थिति में सबसे सफलतापूर्वक विश्लेषित धुरी नियमों के लिए इसमें तेजी से कई कदम उठाने पड़ते हैं। सुचारू विश्लेषण विकसित करने के लिए यह मुख्य प्रेरणाओं में से एक था।<ref name=spielman-teng-2001 />
+सिम्प्लेक्स एल्गोरिदम अभ्यास में एक बहुत ही कुशल एल्गोरिदम है, और यह अभ्यास में लीनियर प्रोग्रामिंग के लिए प्रमुख एल्गोरिदम में से एक है। प्रायोगिक समस्याओं पर, एल्गोरिदम द्वारा उठाए गए कदमों की संख्या चर और बाधाओं की संख्या में लीनियर है।<ref name="shamir" /><ref name="andrei" /> फिर भी सैद्धांतिक रूप से वर्स्ट केस में सबसे सफलतापूर्वक विश्लेषित धुरी नियमों के लिए इसमें तेजी से कई कदम उठाने पड़ते हैं। स्मूथ्द एनालिसिस विकसित करने के लिए यह मुख्य प्रेरणाओं में से एक था।<ref name=spielman-teng-2001 />
-गड़बड़ी मॉडल के लिए, हम मानते हैं कि इनपुट डेटा [[गाऊसी वितरण]] से शोर से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं <math>\bar{\mathbf A} \in \mathbb{R}^{n\times d}, \bar{\mathbf b} \in \mathbb{R}^n, \mathbf c \in \mathbb{R}^d</math> संतुष्ट <math>\|(\bar{\mathbf a}_i, \bar{b}_i)\|_2 \leq 1</math> सभी पंक्तियों के लिए <math>(\bar{\mathbf a}_i, \bar{b}_i)</math> मैट्रिक्स का <math>(\bar{\mathbf A}, \bar{\mathbf b}).</math> ये शोर <math>(\hat{\mathbf A}, \hat{\mathbf b})</math> माध्य के साथ गाऊसी वितरण से नमूना की गई स्वतंत्र प्रविष्टियाँ हैं <math>0</math> और मानक विचलन <math>\sigma</math>. हमलोग तैयार हैं <math>\mathbf A = \bar{\mathbf A} + \hat{\mathbf A}, \mathbf b = \bar{\mathbf b} + \hat{\mathbf b}</math>. सुचारू इनपुट डेटा में रैखिक प्रोग्राम शामिल होता है
+पेरटूरबाशन मॉडल के लिए, हम मानते हैं कि इनपुट डेटा [[गाऊसी वितरण|गाऊसी डिस्ट्रीब्यूशन]]  से ध्वनि से परेशान है। सामान्यीकरण उद्देश्यों के लिए, हम अप्रभावित डेटा मानते हैं <math>\bar{\mathbf A} \in \mathbb{R}^{n\times d}, \bar{\mathbf b} \in \mathbb{R}^n, \mathbf c \in \mathbb{R}^d</math> संतुष्ट <math>\|(\bar{\mathbf a}_i, \bar{b}_i)\|_2 \leq 1</math> सभी पंक्तियों के लिए <math>(\bar{\mathbf a}_i, \bar{b}_i)</math> आव्यूह  का <math>(\bar{\mathbf A}, \bar{\mathbf b}).</math> ये ध्वनि <math>(\hat{\mathbf A}, \hat{\mathbf b})</math> माध्य के साथ गाऊसी डिस्ट्रीबुसन से नमूना की गई स्वतंत्र प्रविष्टियाँ  <math>0</math> और मानक विचलन <math>\sigma</math>. हमने  <math>\mathbf A = \bar{\mathbf A} + \hat{\mathbf A}, \mathbf b = \bar{\mathbf b} + \hat{\mathbf b}</math>.सेट किया है जो स्मूथ्द इनपुट डेटा में लीनियर प्रोग्राम सम्मिलित होता है
 :अधिकतम करें
@@ Line 25: / Line 25: @@
 ::<math>\mathbf A \mathbf{x} \leq \mathbf b</math>.
-यदि डेटा पर हमारे एल्गोरिदम का चलने का समय <math>\mathbf A, \mathbf b, \mathbf c</math> द्वारा दिया गया है <math>T(\mathbf A, \mathbf b,\mathbf c)</math> तो सिंप्लेक्स विधि की सहज जटिलता है<ref>{{Citation | last1=Dadush |first1=Daniel|last2=Huiberts|first2=Sophie|title=A friendly smoothed analysis of the simplex method|year=2018|journal=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing|pages=390–403|arxiv=1711.05667|doi=10.1145/3188745.3188826|isbn=9781450355599}}</ref>
+यदि डेटा पर हमारे एल्गोरिदम का चलने का समय <math>\mathbf A, \mathbf b, \mathbf c</math> द्वारा दिया गया है <math>T(\mathbf A, \mathbf b,\mathbf c)</math> तो सिंप्लेक्स विधि की स्मूथ्द कोम्प्लेक्ससिटी है<ref>{{Citation | last1=Dadush |first1=Daniel|last2=Huiberts|first2=Sophie|title=A friendly smoothed analysis of the simplex method|year=2018|journal=Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing|pages=390–403|arxiv=1711.05667|doi=10.1145/3188745.3188826|isbn=9781450355599}}</ref>
 ::<math>C_s(n,d,\sigma) := \max_{\bar{\mathbf A}, \bar{\mathbf b}, \mathbf c} ~ \mathbb{E}_{\hat{\mathbf A},\hat{\mathbf b}}[T(\bar{\mathbf A} + \hat{\mathbf A}, \bar{\mathbf b} + \hat{\mathbf b}, \mathbf c)] = {\rm poly}(d,\log n, \sigma^{-1}).</math>
-यह सीमा एक विशिष्ट धुरी नियम के लिए है जिसे छाया शीर्ष नियम कहा जाता है। शैडो वर्टेक्स नियम आमतौर पर उपयोग किए जाने वाले धुरी नियमों जैसे कि डेंटज़िग नियम या सबसे तेज किनारे वाले नियम की तुलना में धीमा है<ref name=borgwardt-damm-donig-joas />लेकिन इसमें ऐसे गुण हैं जो इसे संभाव्य विश्लेषण के लिए बहुत उपयुक्त बनाते हैं।<ref name=borgwardt />
+यह सीमा एक विशिष्ट धुरी नियम के लिए है जिसे छाया शीर्ष नियम कहा जाता है। शैडो वर्टेक्स नियम सामान्यत: उपयोग किए जाने वाले धुरी नियमों जैसे कि डेंटज़िग नियम या सबसे तेज किनारे वाले नियम की तुलना में धीमा है<ref name=borgwardt-damm-donig-joas /> किंतु इसमें ऐसे गुण हैं जो इसे संभाव्य एनालिसिस के लिए बहुत उपयुक्त बनाते हैं।<ref name=borgwardt />
-===संयुक्त अनुकूलन के लिए स्थानीय खोज===
+===संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन ===
-कई [[स्थानीय खोज (अनुकूलन)]] एल्गोरिदम का चलने का समय सबसे खराब होता है, लेकिन व्यवहार में वे अच्छा प्रदर्शन करते हैं।<ref>{{Citation |last=Manthey |first=Bodo |title=Smoothed Analysis of Local Search |date=2021 |url=https://www.cambridge.org/core/books/beyond-the-worstcase-analysis-of-algorithms/smoothed-analysis-of-local-search/CA67DD5FE32ABD53898165847C3F86C7 |work=Beyond the Worst-Case Analysis of Algorithms |pages=285–308 |editor-last=Roughgarden |editor-first=Tim |place=Cambridge |publisher=Cambridge University Press |doi=10.1017/9781108637435.018 |isbn=978-1-108-49431-1 |access-date=2022-06-15}}</ref>
+कई [[स्थानीय खोज (अनुकूलन)]] एल्गोरिदम का चलने का समय सबसे व्यर्थ होता है, किंतु अभ्यास में वे अच्छा प्रदर्शन करते हैं।<ref>{{Citation |last=Manthey |first=Bodo |title=Smoothed Analysis of Local Search |date=2021 |url=https://www.cambridge.org/core/books/beyond-the-worstcase-analysis-of-algorithms/smoothed-analysis-of-local-search/CA67DD5FE32ABD53898165847C3F86C7 |work=Beyond the Worst-Case Analysis of Algorithms |pages=285–308 |editor-last=Roughgarden |editor-first=Tim |place=Cambridge |publisher=Cambridge University Press |doi=10.1017/9781108637435.018 |isbn=978-1-108-49431-1 |access-date=2022-06-15}}</ref>
-एक उदाहरण [[ट्रैवलिंग सेल्समैन की समस्या]] के लिए [[2-ऑप्ट]] अनुमानी है। स्थानीय रूप से इष्टतम समाधान मिलने तक इसमें तेजी से कई पुनरावृत्तियां हो सकती हैं, हालांकि व्यवहार में चलने का समय शीर्षों की संख्या में उपवर्गिक है।<ref name="engler-roeglin-voecking" />[[सन्निकटन अनुपात]], जो एल्गोरिदम के आउटपुट की लंबाई और इष्टतम समाधान की लंबाई के बीच का अनुपात है, व्यवहार में अच्छा होता है लेकिन सैद्धांतिक रूप से सबसे खराब स्थिति में भी खराब हो सकता है।
-समस्या उदाहरणों का एक वर्ग दिया जा सकता है <math>n</math> बॉक्स में अंक <math>[0,1]^d</math>, जहां उनकी जोड़ीदार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई व्यक्ति गड़बड़ी मॉडल का विश्लेषण कर सकता है जहां कोने <math>v_1,\dots,v_n</math> संभाव्यता घनत्व फ़ंक्शन के साथ संभाव्यता वितरण के अनुसार स्वतंत्र रूप से नमूना लिया जाता है <math>f_1,\dots,f_n : [0,1]^d \rightarrow [0,\theta]</math>. के लिए <math>\theta = 1</math>, अंक समान रूप से वितरित किए जाते हैं। कब <math>\theta > 1</math> बड़ा होने पर, प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस गड़बड़ी मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात, के बहुपद कार्यों से बंधे हैं <math>n</math> और <math>\theta</math>.<ref name="engler-roeglin-voecking" />
+एक उदाहरण [[ट्रैवलिंग सेल्समैन की समस्या]] के लिए [[2-ऑप्ट]] अनुमानी है। स्थानीय रूप से इष्टतम समाधान मिलने तक इसमें तेजी से कई पुनरावृत्तियां हो सकती हैं, चूँकि अभ्यास में चलने का समय वेर्टिसस की संख्या में सबक्वाड्रैटीक है।<ref name="engler-roeglin-voecking" /> [[सन्निकटन अनुपात|अप्प्रोक्सिमेसन  रेश्यो]], जो एल्गोरिदम के आउटपुट की लंबाई और इष्टतम समाधान की लंबाई के बीच का अनुपात है, अभ्यास में अच्छा होता है किंतु सैद्धांतिक रूप से वर्स्ट केस में भी व्यर्थ हो सकता है।
-एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए सुचारू विश्लेषण सफल रहा, वह है k-मीन्स क्लस्टरिंग#Standard_algorithm_(naive_k-means)|k-मीन्स विधि। दिया गया <math>n</math> में अंक <math>[0,1]^d</math>, एक ही क्लस्टर में बिंदुओं के बीच छोटी जोड़ीदार दूरी वाले समूहों में एक अच्छा विभाजन ढूंढना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और व्यवहार में बहुत तेज़ है, हालाँकि इसमें समय लग सकता है <math>e^{\Omega(n)}</math> सबसे खराब स्थिति में स्थानीय स्तर पर इष्टतम समाधान खोजने के लिए पुनरावृत्तियाँ। हालाँकि, यह मानते हुए कि बिंदुओं का स्वतंत्र गाऊसी वितरण है, प्रत्येक में अपेक्षा है <math>[0,1]^d</math> और मानक विचलन <math>\sigma</math>, एल्गोरिथ्म के पुनरावृत्तियों की अपेक्षित संख्या एक बहुपद से घिरी हुई है <math>n</math>, <math>d</math> और <math>\sigma</math>.
+समस्या उदाहरणों का एक वर्ग बॉक्स <math>[0,1]^d</math> में <math>n</math> बिंदुओं द्वारा दिया जा सकता है,  जहां उनकी जोड़ीदार दूरियां एक नॉर्म (गणित) से आती हैं। पहले से ही दो आयामों में, 2-ऑप्ट अनुमान स्थानीय इष्टतम खोजने तक तेजी से कई पुनरावृत्तियों को ले सकता है। इस सेटिंग में, कोई पेरटूरबाशन मॉडल का विश्लेषण कर सकता है जहां कोने <math>v_1,\dots,v_n</math> को प्रोबब्लिटी डेंसिटी फ़ंक्शन <math>f_1,\dots,f_n : [0,1]^d \rightarrow [0,\theta]</math> के साथ युनिफोर्मिली डिस्ट्रीबुसन के अनुसार स्वतंत्र रूप से नमूना किया जाता है। <math>\theta = 1</math> के लिए, अंक समान रूप से वितरित किए गए हैं। जब <math>\theta > 1</math> बड़ा होता है, तो प्रतिद्वंद्वी के पास कठिन समस्या की संभावना को बढ़ाने की अधिक क्षमता होती है। इस पेरटूरबाशन मॉडल में, 2-ऑप्ट हेयुरिस्टिक के पुनरावृत्तियों की अपेक्षित संख्या, साथ ही परिणामी आउटपुट के अनुमानित अनुपात,  <math>n</math> और <math>\theta</math> के बहुपद कार्यों से बंधे हैं।<ref name="engler-roeglin-voecking" />
-<ref name=david-manthey-roeglin />
+एक अन्य स्थानीय खोज एल्गोरिदम जिसके लिए स्मूथ्द एनालिसिस सफल रहा वह के-मीन्स विधि है।<math>[0,1]^d</math> में <math>n</math> अंक दिए जाने पर, एक ही क्लस्टर में बिंदुओं के बीच छोटी जोड़ीदार दूरी वाले समूहों में एक अच्छा विभाजन खोजना एनपी-कठिन है। लॉयड का एल्गोरिदम व्यापक रूप से उपयोग किया जाता है और अभ्यास में बहुत तेज़ है, चूँकि यह स्थानीय रूप से इष्टतम समाधान खोजने के लिए सबसे वर्स्ट केस में पुनरावृत्तियों को ले सकता है। चूँकि यह मानते हुए कि बिंदुओं में स्वतंत्र गॉसियन डिस्ट्रीबुसन हैं, प्रत्येक की अपेक्षा <math>[0,1]^d</math> और मानक विचलन <math>\sigma</math> है, एल्गोरिदम के पुनरावृत्तियों की अपेक्षित संख्या  <math>n</math>, <math>d</math> और <math>\sigma</math>. में एक बहुपद से घिरी है।<ref name="david-manthey-roeglin" />
 ==यह भी देखें==
-*[[औसत-मामले की जटिलता]]
+*एवरेज केस कॉम्पलेक्ससिटी
-*छद्म-बहुपद समय
+*सूडो -पालीनोमिअल टाइम
-*[[सबसे खराब स्थिति जटिलता]]
+*[[सबसे खराब स्थिति जटिलता|वर्स्ट केस कॉम्पलेक्ससिटी]]
 ==संदर्भ==

Anonymous

Search

स्मूथ्द एनालिसिस: Difference between revisions

Namespaces

More

Page actions

Revision as of 10:59, 21 July 2023

Contents

इतिहास

उदाहरण

लीनियर प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

स्मूथ्द एनालिसिस: Difference between revisions

Revision as of 10:59, 21 July 2023

इतिहास

उदाहरण

लीनियर प्रोग्रामिंग के लिए सिंप्लेक्स एल्गोरिदम

संयुक्त अनुकूलन के लिए कोम्बिनाटोरिअल ओप्टीमायजैसन

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories