बिग ओ अंकन: Difference between revisions

Latest revision as of 17:35, 19 September 2023

बिगओनोटेशन का उदाहरण:

{\color {red}f(x)}\in O{\color {blue}(g(x))}

जैसा कि वहां उपस्थित है

M>0

(जैसे,

M=1

) और

x_{0}

(जैसे,

x_{0}=5

) ऐसा है कि

{\color {red}f(x)}\leq {\color {blue}Mg(x)}

जब कभी भी

x\geq x_{0}

.

बिग O संकेतन एक गणितीय संकेतन है जो किसी फलन के सीमित व्यवहार का वर्णन करता है जब तर्क किसी विशिष्ट मूल्य या अनन्तता की ओर प्रवृत होता है। बिग ओ पॉल गुस्ताव^[1],एडमंड लैंडौ^[2]और अन्य द्वारा आविष्कार संबंधित अनंतस्पर्शी संकेतन पद्धति का सदस्य है,जिन्हें सामूहिक रूप से बैचमैन-लैंडौ संकेतन या अनंतस्पर्शी संकेतन कहा जाता है। अक्षर O को बैचमैन द्वारा चुना गया था का प्रतीकऑर्डनंग है जिसका अर्थ सन्निकटन का क्रम है।

कंप्यूटर विज्ञान में, बिग O संकेतन का उपयोग कलन विधि को वर्गीकृत करने के लिए किया जाता है,जिसके अनुसार कैसे उनके रन टाइम या रिक्त स्थान की आवश्यकताएं निविष्ट के आकार के बढ़ने के साथ बढ़ती हैं।^[3]विश्लेषणात्मक संख्या सिद्धांत में,बिग O संकेतन का उपयोग अधिकांशतः अंकगणितीय फलन और एक बेहतर समझी गई सन्निकटन के बीच अंतर पर सीमा व्यक्त करने के लिए किया जाता है; इस तरह के अंतर का प्रसिद्ध उदाहरण अभाज्य संख्या प्रमेय में शेष पद है।समान अनुमान प्रदान करने के लिए कई अन्य क्षेत्रों में भी बिग O संकेतन का उपयोग किया जाता है।

बिग O संकेतन उनकी विकास दर के अनुसार फलनों को चित्रित करता है: समान अनंतस्पर्शी वृद्धि दर वाले विभिन्न फलनों को ही O संकेतन का उपयोग करके दर्शाया जा सकता है।अक्षर 'O' का उपयोग किया जाता है क्योंकि किसी फलन की वृद्धि दर को फलन का क्रम भी कहा जाता है।बिग O संकेतन के संदर्भ में किसी फलन का विवरण सामान्यतः फलन की वृद्धि दर पर केवल ऊपरी सीमा प्रदान करना है।

बिग O संकेतन के साथ संबद्ध कई संबंधित संकेतन हैं जो अनंतस्पर्शी वृद्धि दर पर अन्य प्रकार की सीमाओं का वर्णन करने के लिए प्रतीकों $o, Ω, ω$ , और $Θ$ का प्रयोग करते हैं।

औपचारिक परिभाषा

माना $f$ , जिस फलन का अनुमान लगाया जाना है, वह वास्तविक संख्या या जटिल संख्या के मान वाल�

[1]

[2]

[3]

@@ Line 46: / Line 46: @@
 या
 :<math>T(n) \in O(n^2) </math>
-और कहें कि एल्गोरिदम का क्रम है {{math|n<sup>2</sup>}} समय जटिलता. संकेत का अभिप्राय अपने सामान्य गणितीय अर्थ में सामान्य को व्यक्त करना नहीं है, किन्तु अधिक बोलचाल की भाषा है, इसलिए दूसरी अभिव्यक्ति को कभी-कभी अधिक स्पष्ट माना जाता है (नीचे सामान्य चिह्न चर्चा देखें) जबकि पहली को कुछ लोगों द्वारा दुरुपयोग माना जाता है .<ref name="clrs3" />
+और कहें कि एल्गोरिदम का क्रम है {{math|n<sup>2</sup>}} समय जटिलता. संकेत का अभिप्राय अपने सामान्य गणितीय अर्थ में सामान्य को व्यक्त करना नहीं है, किन्तु अधिक बोलचाल की भाषा है, इसलिए दूसरी अभिव्यक्ति को कभी-कभी अधिक स्पष्ट माना जाता है (नीचे सामान्य चिह्न चर्चा देखें) जबकि पहली को कुछ लोगों द्वारा दुरुपयोग माना जाता है .
 === अनंतिम स्पर्शोन्मुखता ===
 बिगओका उपयोग टेलर श्रृंखला अनुमान त्रुटि और गणितीय फलन के सन्निकटन में अभिसरण का वर्णन करने के लिए भी किया जा सकता है। सबसे महत्वपूर्ण शब्दों को स्पष्ट रूप से लिखा जाता है, और फिर सबसे कम महत्वपूर्ण शब्दों को बड़े O शब्द में संक्षेपित किया जाता है। उदाहरण के लिए, एक्सपोनेंशियल फलन औपचारिक परिभाषा और इसकी दो अभिव्यक्तियों पर विचार करें जो कब मान्य हैं
@@ Line 239: / Line 239: @@
 कंप्यूटर विज्ञान बड़ा उपयोग करता है <math>O   </math>, बड़ी थीटा <math>\Theta   </math>, थोड़ा <math>o   </math>, थोड़ा ओमेगा <math>\omega   </math> और नुथ का बड़ा ओमेगा <math>\Omega   </math> संकेतन.<ref>{{Introduction to Algorithms|edition=2|pages=41–50}}</ref> विश्लेषणात्मक संख्या सिद्धांत अधिकांशतः बड़े का उपयोग करता है <math>O   </math>, छोटा <math>o   </math>, हार्डी-लिटलवुड का बड़ा ओमेगा <math>\Omega   </math> (+, − या ± सबस्क्रिप्ट के साथ या उसके बिना) और <math>\sim</math> संकेतन.<ref name=Ivic/> छोटा ओमेगा <math>\omega   </math> विश्लेषण में अंकन का प्रयोग उतनी बार नहीं किया जाता है।<ref>for example it is omitted in: {{cite web |last1=Hildebrand |first1=A.J. |title=Asymptotic Notations |url=http://www.math.uiuc.edu/~ajh/595ama/ama-ch2.pdf |website=Asymptotic Methods in Analysis |series=Math&nbsp;595, Fall 2009 |publisher=University of Illinois |place=Urbana, IL |department=Department of Mathematics |access-date=14 March 2017 |archive-date=14 March 2017 |archive-url=https://web.archive.org/web/20170314153801/http://www.math.uiuc.edu/~ajh/595ama/ama-ch2.pdf |url-status=live }}</ref>
-[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category:CS1 Deutsch-language sources (de)]]
-[[Category:CS1 maint]]
-[[Category:Created On 23/06/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Missing redirects]]
-[[Category:Pages with ignored display titles]]
-[[Category:Pages with math errors]]
-[[Category:Pages with math render errors]]
-== Orders of common functions ==
-{{Further|Time complexity#Table of common time complexities}}
-Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm.  In each case, ''c'' is a positive constant and ''n'' increases without bound. The slower-growing functions are generally listed first.
-{| class="wikitable"
-|-
-!Notation !! Name !! Example
-|-
-|<math>O(1)</math> || [[Constant time|constant]] || Determining if a binary number is even or odd; Calculating <math>(-1)^n</math>; Using a constant-size [[lookup table]]
-|-
-|<math>O(\log \log n)</math> || double logarithmic || Average number of comparisons spent finding an item using [[interpolation search]] in a sorted array of uniformly distributed values
-|-
-|<math>O(\log n)</math> || [[Logarithmic time|logarithmic]] || Finding an item in a sorted array with a [[Binary search algorithm|binary search]] or a balanced search [[Tree data structure|tree]] as well as all operations in a [[binomial heap]]
-|-
-|<math>O((\log n)^c)</math><br /><math display=inline> c>1</math> || [[Polylogarithmic time|polylogarithmic]] || Matrix chain ordering can be solved in polylogarithmic time on a [[parallel random-access machine]].
-|-
-|<math>O(n^c)</math><br /><math display=inline> 0<c<1</math> || fractional power || Searching in a [[k-d tree]]
-|-
-|<math>O(n)</math> || [[linear time|linear]] || Finding an item in an unsorted list or in an unsorted array; adding two ''n''-bit integers by [[Ripple carry adder|ripple carry]]
-|-
-|<math>O(n\log^* n)</math> || ''n'' [[log-star]] ''n'' || Performing [[Polygon triangulation|triangulation]] of a simple polygon using [[Kirkpatrick–Seidel algorithm|Seidel's algorithm]], where <math>\log^*(n) =
-\begin{cases}
-, & \text{if }n \leq 1 \\
-+ \log^*(\log n), & \text{if }n>1
-\end{cases}</math>
-|-
-|<math>O(n\log n) = O(\log n!)</math> || [[Linearithmic time|linearithmic]], loglinear, quasilinear, or "''n'' log ''n''" || Performing a [[fast Fourier transform]]; fastest possible [[comparison sort]]; [[heapsort]] and [[merge sort]]
-|-
-|<math>O(n^2)</math> || [[quadratic time|quadratic]] || Multiplying two ''n''-digit numbers by [[Multiplication_algorithm#Long_multiplication|schoolbook multiplication]]; simple sorting algorithms, such as [[bubble sort]], [[selection sort]] and [[insertion sort]]; (worst-case) bound on some usually faster sorting algorithms such as [[quicksort]], [[Shellsort]], and [[tree sort]]
-|-
-|<math>O(n^c)</math> || [[polynomial time|polynomial]] or algebraic || [[Tree-adjoining grammar]] parsing; maximum [[Matching (graph theory)|matching]] for [[bipartite graph]]s; finding the [[determinant]] with [[LU decomposition]]
-|-
-|<math>L_n[\alpha,c] = e^{(c + o(1)) (\ln n)^\alpha (\ln \ln n)^{1-\alpha}}</math><br /><math display=inline> 0 < \alpha < 1</math> || [[L-notation]] or [[sub-exponential time|sub-exponential]] || Factoring a number using the [[quadratic sieve]] or [[number field sieve]]
-|-
-|<math>O(c^n)</math><br/><math display=inline> c>1</math> || [[exponential time|exponential]] || Finding the (exact) solution to the [[travelling salesman problem]] using [[dynamic programming]]; determining if two logical statements are equivalent using [[brute-force search]]
-|-
-|<math>O(n!)</math> || [[factorial]] || Solving the [[travelling salesman problem]] via brute-force search; generating all unrestricted permutations of a [[Partially ordered set|poset]]; finding the [[determinant]] with [[Laplace expansion]]; enumerating [[Bell number|all partitions of a set]]
-|}
-The statement <math>f(n) = O(n!)</math> is sometimes weakened to <math>f(n) = O\left(n^n\right)</math> to derive simpler formulas for asymptotic complexity. For any <math>k>0</math> and {{nowrap|<math>c > 0</math>,}} <math>O(n^c(\log n)^k)</math> is a subset of <math>O(n^{c+\varepsilon})</math> for any {{nowrap|<math> \varepsilon > 0</math>,}} so may be considered as a polynomial with some bigger order.
-[[Category:Articles with hatnote templates targeting a nonexistent page]]
-[[Category:CS1 Deutsch-language sources (de)]]
-[[Category:CS1 maint]]
-[[Category:Created On 23/06/2023]]
-[[Category:Machine Translated Page]]
-[[Category:Missing redirects]]
-[[Category:Pages with ignored display titles]]
-[[Category:Pages with math errors]]
-[[Category:Pages with math render errors]]
-=== कंप्यूटर विज्ञान में उपयोग ===
-{{Further|एल्गोरिदम का विश्लेषण}}
-अनौपचारिक रूप से, विशेष रूप से कंप्यूटर विज्ञान में, बड़े O नोटेशन का उपयोग अधिकांशतः एसिम्प्टोटिक ऊपरी और निचले सीमा # तंग सीमा का वर्णन करने के लिए कुछ अलग विधि से किया जा सकता है, जहां बड़े थीटा Θ नोटेशन का उपयोग किसी दिए गए संदर्भ में तथ्यात्मक रूप से अधिक उपयुक्त हो सकता है। उदाहरण के लिए, किसी फलन T(n) = 73n<sup>3</sup>+22n<sup>2</sup> + 58 पर विचार करते समय, निम्नलिखित में से सभी सामान्यतः स्वीकार्य हैं, किन्तु कड़ी सीमाएं (जैसे नीचे संख्या 2 और 3) सामान्यतः सरल सीमाओं (जैसे नीचे संख्या 1) की तुलना में दृढ़ता से पसंद की जाती हैं।
-#{{nowrap|1=''T''(''n'') = ''O''(''n''<sup>100</sup>)}}
-#{{nowrap|1=''T''(''n'') = ''O''(''n''<sup>3</sup>)}}
-#{{nowrap|1=''T''(''n'') = Θ(''n''<sup>3</sup>)}}
-समतुल्य अंग्रेजी कथन क्रमशः हैं:
-#T(n) बिना किसी लक्षण के n<sup>100</sup> से अधिक तेजी से बढ़ता है
-#T(n) बिना किसी लक्षण के n<sup>3</sup> से अधिक तेजी से बढ़ता है
-#T(n) n<sup>3</sup> जितनी तेजी से लक्षणहीन रूप से बढ़ता है.
-इसलिए जबकि तीनों कथन सत्य हैं, प्रत्येक में उत्तरोत्तर अधिक जानकारी समाहित है। चूँकि, कुछ क्षेत्रों में, बड़े O नोटेशन (उपरोक्त सूचियों में नंबर 2) का उपयोग बड़े थीटा नोटेशन (उपरोक्त सूचियों में आइटम नंबर 3) की तुलना में अधिक सामान्यतः किया जाएगा। उदाहरण के लिए, यदि टी (n) इनपुट आकार n के लिए नए विकसित एल्गोरिदम के चलने के समय का प्रतिनिधित्व करता है, तो एल्गोरिदम के आविष्कारक और उपयोगकर्ता ऊपरी एसिम्प्टोटिक बाउंड लगाने के इच्छुक हो सकते हैं कि इसे चलाने में कितना समय लगेगा। निचली स्पर्शोन्मुख सीमा के बारे में स्पष्ट कथन।
-=== अन्य संकेतन ===
-अपनी पुस्तक [[एल्गोरिदम का परिचय]] में, थॉमस एच. कॉर्मेन, चार्ल्स ई. लेइसर्सन, रोनाल्ड एल. रिवेस्ट और [[क्लिफोर्ड स्टीन]] ने फलन के सेट पर विचार किया है जो संतुष्ट करता है
-:<math> f(n) = O(g(n))\quad(n\to\infty)~.</math>
-उदाहरण के लिए, सही संकेतन में इस सेट को O(g) कहा जा सकता है, जहाँ
-<math display=block>O(g) = \{ f : \text{there exist positive constants}~c~\text{and}~n_0~\text{such that}~0 \le f(n) \le c g(n) \text{ for all } n \ge n_0 \}.</math><ref>{{cite book |  isbn=978-0-262-53305-8 |author1=Cormen, Thomas H. |author2=Leiserson, Charles E. |author3=Rivest, Ronald L. |title=एल्गोरिदम का परिचय|location=Cambridge/MA |publisher=MIT Press |edition=3rd |year=2009 |page=47 |quote=When we have only an asymptotic upper bound, we use O-notation. For a given function ''g''(''n''), we denote by ''O''(''g''(''n'')) (pronounced "big-oh of ''g'' of ''n''" or sometimes just "oh of ''g'' of ''n''") the set of functions ''O''(''g''(''n'')) = { ''f''(''n'') : there exist positive constants ''c'' and ''n''<sub>0</sub> such that 0 ≤ ''f''(''n'') ≤ ''cg''(''n'') for all ''n'' ≥ ''n''<sub>0</sub>} }}</ref>
-लेखकों का कहना है कि सेट सदस्यता ऑपरेटर (∈) के अतिरिक्त सेट सदस्यता को दर्शाने के लिए समानता ऑपरेटर (=) का उपयोग नोटेशन का दुरुपयोग है, किन्तु ऐसा करने के लाभ हैं।<ref name="clrs3">{{cite book |isbn=978-0-262-53305-8 |author1=Cormen,Thomas H. |author2=Leiserson, Charles E. |author3=Rivest, Ronald L. |title=एल्गोरिदम का परिचय|url=https://archive.org/details/introductiontoal00corm_805 |url-access=limited |location=Cambridge/MA |publisher=MIT Press |edition=3rd |year=2009 |page=[https://archive.org/details/introductiontoal00corm_805/page/n65 45] |quote=Because ''θ''(''g''(''n'')) is a set, we could write "''f''(''n'') ∈ ''θ''(''g''(''n''))" to indicate that ''f''(''n'') is a member of ''θ''(''g''(''n'')). Instead, we will usually write ''f''(''n'') = ''θ''(''g''(''n'')) to express the same notion. You might be confused because we abuse equality in this way, but we shall see later in this section that doing so has its advantages.}}</ref> किसी समीकरण या असमानता के अंदर, एसिम्प्टोटिक नोटेशन का उपयोग सेटO (जी) में अज्ञात फलन के लिए होता है, जो निम्न-क्रम वाले शब्दों को समाप्त करता है, और समीकरणों में अनावश्यक अव्यवस्था को कम करने में मदद करता है, उदाहरण के लिए:<ref>{{cite book |isbn=978-0-262-53305-8 |author1=Cormen,Thomas H. |author2=Leiserson, Charles E. |author3=Rivest, Ronald L. |title=एल्गोरिदम का परिचय|url=https://archive.org/details/introductiontoal00corm_805 |url-access=limited |location=Cambridge/MA |publisher=MIT Press |edition=3rd |year=2009 |page=[https://archive.org/details/introductiontoal00corm_805/page/n69 49] |quote=When the asymptotic notation stands alone (that is, not within a larger formula) on the right-hand side of an equation (or inequality), as in n = O(n<sup>2</sup>), we have already defined the equal sign to mean set membership: n ∈ O(n<sup>2</sup>). In general, however, when asymptotic notation appears in a formula, we interpret it as standing for some anonymous function that we do not care to name. For example, the formula 2''n''<sup>2</sup> + 3''n'' + 1 = 2''n''<sup>2</sup> + ''θ''(''n'') means that 2''n''<sup>2</sup> + 3''n'' + 1 = 2''n''<sup>2</sup> + ''f''(''n''), where ''f''(''n'') is some function in the set ''θ''(''n''). In this case, we let ''f''(''n'') = 3''n'' + 1, which is indeed in ''θ''(''n''). Using asymptotic notation in this manner can help eliminate inessential detail and clutter in an equation.}}</ref>
-:<math> 2n^2 + 3n + 1=2n^2 + O(n).</math>
-=== बाचमैन-लैंडौ नोटेशन का विस्तार ===
-कंप्यूटर विज्ञान में कभी-कभी उपयोग किया जाने वाला अन्य संकेतन Õ (सॉफ्ट-ओ पढ़ें) है, जो पॉलीलॉगरिदमिक कारकों को छुपाता है। उपयोग में दो परिभाषाएँ हैं: कुछ लेखक f(n)=Õ(g(n)) को [[आशुलिपि]] के रूप में उपयोग करते हैं {{nowrap|1=''f''(''n'') = ''O''(''g''(''n'') [[Polylogarithmic function|log<sup>''k''</sup> ''n'']])}} कुछ k के लिए, जबकि अन्य इसे शॉर्टहैंड के रूप में उपयोग करते हैं {{nowrap|1=''f''(''n'') = ''O''(''g''(''n'') log<sup>''k''</sup> ''g''(''n''))}}.<ref>{{Cite book |last1=Cormen |first1=Thomas H. |url=https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ |title=एल्गोरिदम का परिचय|last2=Leiserson |first2=Charles E. |last3=Rivest |first3=Ronald L. |last4=Stein |first4=Clifford |publisher=The MIT Press |year=2022 |isbn=9780262046305 |edition=4th |location=Cambridge, Mass. |pages=74–75 |oclc= |url-access=}}</ref> कब {{Nowrap|''g''(''n'')}} n में बहुपद है, कोई अंतर नहीं है;चूँकि, बाद वाली परिभाषा किसी को यह कहने की अनुमति देती है, उदाहरण के लिए वह <math>n2^n = \tilde O(2^n)</math> जबकि पूर्व परिभाषा इसकी अनुमति देती है <math>\log^k n = \tilde O(1)</math> किसी स्थिरांक k के लिए। कुछ लेखकO लिखते हैं<sup>*</sup>बाद वाली परिभाषा के समान उद्देश्य के लिए।<ref>{{cite journal | url=https://www.cs.helsinki.fi/u/mkhkoivi/publications/sicomp-2009.pdf | author=Andreas Björklund and Thore Husfeldt and Mikko Koivisto | title=समावेशन-बहिष्करण के माध्यम से विभाजन निर्धारित करें| journal=[[SIAM Journal on Computing]] | volume=39 | number=2 | pages=546&ndash;563 | year=2009 | doi=10.1137/070683933 | access-date=2022-02-03 | archive-date=2022-02-03 | archive-url=https://web.archive.org/web/20220203095918/https://www.cs.helsinki.fi/u/mkhkoivi/publications/sicomp-2009.pdf | url-status=live }} See sect.2.3, p.551.</ref> अनिवार्य रूप से, यह बड़ा O नोटेशन है, [[पॉलीलॉगरिदमिक फ़ंक्शन|पॉलीलॉगरिदमिक फलन]] को अनदेखा कर रहा है क्योंकि एसिम्प्टोटिक विश्लेषण | कुछ अन्य सुपर-लघुगणकीय फलन के विकास-दर प्रभाव बड़े आकार के इनपुट मापदंड के लिए विकास-दर विस्फोट का संकेत देते हैं जो खराब रन-टाइम प्रदर्शन की पूर्वानुमान करने के लिए अधिक महत्वपूर्ण है लघुगणक-विकास कारक (ओं) द्वारा योगदान किए गए उत्तम-बिंदु प्रभावों की तुलना में। इस संकेतन का उपयोग अधिकांशतः विकास-दर के अन्दर होने वाली खामियों को दूर करने के लिए किया जाता है, जिन्हें वर्तमान स्थितियों के लिए बहुत कसकर बांधा गया है (लॉग के बाद से) किसी भी स्थिरांक k और किसी के लिए {{nowrap|''ε'' > 0}}).
-इसके अतिरिक्त एल-नोटेशन, के रूप में परिभाषित किया गया है
-:<math>L_n[\alpha,c] = e^{(c + o(1))(\ln n)^\alpha(\ln\ln n)^{1-\alpha}}</math>
-उन फलनों के लिए सुविधाजनक है जो समय जटिलता#बहुपद समय और समय जटिलता#घातीय समय के बीच हैं {{nowrap|<math>\ln n</math>.}}
 == सामान्यीकरण और संबंधित उपयोग ==
@@ Line 392: / Line 322: @@
 *[https://autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ An example of BigO in accuracy of central divided difference scheme for first derivative] {{Webarchive|url=https://web.archive.org/web/20181007223123/https://autarkaw.org/2013/01/30/making-sense-of-the-big-oh/ |date=2018-10-07 }}
 *[https://discrete.gr/complexity/ A Gentle Introduction to Algorithm Complexity Analysis]
-|}
 [[Category:Articles with hatnote templates targeting a nonexistent page]]
@@ Line 404: / Line 327: @@
 [[Category:CS1 maint]]
 [[Category:Created On 23/06/2023]]
+[[Category:Lua-based templates]]
 [[Category:Machine Translated Page]]
 [[Category:Missing redirects]]
@@ Line 409: / Line 333: @@
 [[Category:Pages with math errors]]
 [[Category:Pages with math render errors]]
+[[Category:Pages with reference errors]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Webarchive template wayback links]]

Anonymous

Search

बिग ओ अंकन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 17:35, 19 September 2023

Contents

औपचारिक परिभाषा