बिग ओ अंकन

Error creating thumbnail:

बिग ओ नोटेशन का उदाहरण: ${\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 को बैचमैन द्वारा :विक्ट:ऑर्डनंग#जर्मन के लिए चुना गया था, जिसका अर्थ सन्निकटन का क्रम है।

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

बिग ओ नोटेशन उनकी विकास दर के अनुसार कार्यों को चित्रित करता है: समान एसिम्प्टोटिक विकास दर वाले विभिन्न कार्यों को ही ओ नोटेशन का उपयोग करके दर्शाया जा सकता है। O अक्षर का उपयोग इसलिए किया जाता है क्योंकि किसी फ़ंक्शन की वृद्धि दर को फ़ंक्शन का क्रम भी कहा जाता है। बड़े O नोटेशन के संदर्भ में किसी फ़ंक्शन का विवरण आमतौर पर केवल फ़ंक्शन की वृद्धि दर पर ऊपरी सीमा प्रदान करता है।

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

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

होने देना $f$, जिस फ़ंक्शन का अनुमान लगाया जाना है, वह वास्तविक संख्या या जटिल संख्या मूल्यवान फ़ंक्शन हो और चलो $g$, तुलना फ़ंक्शन, वास्तविक मूल्यवान फ़ंक्शन बनें। मान लीजिए कि दोनों कार्यों को सकारात्मक वास्तविक संख्याओं के कुछ बंधे हुए सबसेट उपसमुच्चय पर परिभाषित किया गया है, और $g(x)$ के सभी बड़े पर्याप्त मूल्यों के लिए सख्ती से सकारात्मक रहें $x$. लिखता है

$$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty$$

और इसे पढ़ा जाता है$f(x)$ का बड़ा O है $g(x)$यदि का निरपेक्ष मान $f(x)$ का अधिकतम धनात्मक अचर गुणज है $g(x)$ सभी पर्याप्त रूप से बड़े मूल्यों के लिए $x$. वह है, $f(x)=O{\bigl (}g(x){\bigr )}$ यदि कोई सकारात्मक वास्तविक संख्या मौजूद है $M$ और वास्तविक संख्या $x_{0}$ ऐसा है कि

$$|f(x)|\leq Mg(x)\quad {\text{ for all }}x\geq x_{0}.$$

कई संदर्भों में, यह धारणा कि हम चर के रूप में विकास दर में रुचि रखते हैं $x$ अनंत तक जाता है, उसे अघोषित छोड़ दिया जाता है, और कोई इसे और अधिक सरलता से लिखता है

$$f(x)=O{\bigl (}g(x){\bigr )}.$$

नोटेशन का उपयोग के व्यवहार का वर्णन करने के लिए भी किया जा सकता है $f$ किसी वास्तविक संख्या के निकट $a$ (अक्सर, $a=0$): हम कहते हैं

$$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a$$

यदि सकारात्मक संख्याएँ मौजूद हैं $\delta$ और $M$ ऐसा कि सभी के लिए परिभाषित है $x$ साथ $0<|x-a|<\delta$,

$$|f(x)|\leq Mg(x).$$

जैसा $g(x)$ के ऐसे मूल्यों के लिए सख्ती से सकारात्मक होने के लिए चुना गया है $x$, इन दोनों परिभाषाओं को सीमा श्रेष्ठ का उपयोग करके एकीकृत किया जा सकता है:

$$f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a$$

अगर

$$\limsup _{x\to a}{\frac {\left|f(x)\right|}{g(x)}}<\infty .$$

और इन दोनों परिभाषाओं में सीमा बिंदु $a$ (चाहे $\infty$ या नहीं) के डोमेन का क्लस्टर बिंदु है $f$ और $g$, मैं। ई., के हर पड़ोस में $a$ इसमें अपरिमित रूप से कई बिंदु समान होने चाहिए। इसके अलावा, जैसा कि लिमिट अवर और लिमिट सुपीरियर#रियल-वैल्यूड फ़ंक्शंस के बारे में लेख में बताया गया है $\textstyle \limsup _{x\to a}$ (कम से कम विस्तारित वास्तविक संख्या रेखा पर) हमेशा मौजूद रहता है।

कंप्यूटर विज्ञान में, थोड़ी अधिक प्रतिबंधात्मक परिभाषा आम है: $f$ और $g$ क्या दोनों को प्राकृतिक संख्याओं के कुछ असंबद्ध उपसमुच्चय से गैर-ऋणात्मक वास्तविक संख्याओं तक फलन होना आवश्यक है; तब $f(x)=O{\bigl (}g(x){\bigr )}$ यदि धनात्मक पूर्णांक संख्याएँ मौजूद हैं $M$ और $n_{0}$ ऐसा है कि $f(n)\leq Mg(n)$ सभी के लिए $n\geq n_{0}$.

उदाहरण

सामान्य उपयोग में O अंकन स्पर्शोन्मुख है, अर्थात यह बहुत बड़े को संदर्भित करता है x. इस सेटिंग में, सबसे तेज़ी से बढ़ने वाले शब्दों का योगदान अंततः अन्य को अप्रासंगिक बना देगा। परिणामस्वरूप, निम्नलिखित सरलीकरण नियम लागू किए जा सकते हैं:

• अगर f(x) कई पदों का योग है, यदि सबसे अधिक वृद्धि दर वाला कोई है, तो उसे रखा जा सकता है, और अन्य सभी को छोड़ दिया जा सकता है।
• अगर f(x) कई कारकों का उत्पाद है, किसी भी स्थिरांक (उत्पाद में ऐसे कारक जो निर्भर नहीं होते हैं x) मिटाया जा सकता है।

उदाहरण के लिए, चलो f(x) = 6x⁴ − 2x³ + 5, और मान लीजिए कि हम इसका उपयोग करके इस फ़ंक्शन को सरल बनाना चाहते हैं O संकेतन, इसकी वृद्धि दर को इस प्रकार वर्णित करने के लिए x अनंत तक पहुंचता है। यह फ़ंक्शन तीन पदों का योग है: 6x⁴, −2x³, और 5. इन तीन शर्तों में से, उच्चतम विकास दर वाला वह है जिसके कार्य के रूप में सबसे बड़ा प्रतिपादक है x, अर्थात् 6x⁴. अब कोई दूसरा नियम लागू कर सकता है: 6x⁴ का उत्पाद है 6 और x⁴ जिसमें पहला कारक निर्भर नहीं करता x. इस कारक को छोड़ने पर परिणाम सरलीकृत हो जाता है x⁴. इस प्रकार, हम ऐसा कहते हैं f(x) का बड़ा O है x⁴. गणितीय रूप से हम लिख सकते हैं f(x) = O(x⁴). कोई औपचारिक परिभाषा का उपयोग करके इस गणना की पुष्टि कर सकता है: चलो f(x) = 6x⁴ − 2x³ + 5 और g(x) = x⁴. उपरोक्त से #औपचारिक परिभाषा को लागू करते हुए कथन कि f(x) = O(x⁴) इसके विस्तार के बराबर है,

$$|f(x)|\leq Mx^{4}$$

किसी वास्तविक संख्या के कुछ उपयुक्त विकल्प के लिए x₀ और सकारात्मक वास्तविक संख्या M और सभी के लिए x > x₀. इसे साबित करने के लिए आइए x₀ = 1 और M = 13. फिर, सभी के लिए x > x₀:

$${\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}$$

इसलिए

$$|6x^{4}-2x^{3}+5|\leq 13x^{4}.$$

उपयोग

बिग ओ नोटेशन के अनुप्रयोग के दो मुख्य क्षेत्र हैं:

• गणित में, इसका उपयोग आमतौर पर बिग ओ नोटेशन#इनफिनिटेसिमल एसिम्प्टोटिक्स का वर्णन करने के लिए किया जाता है, विशेष रूप से काटे गए टेलर श्रृंखला या एसिम्प्टोटिक विस्तार के मामले में
• कंप्यूटर विज्ञान में, यह बिग ओ नोटेशन#अनंत स्पर्शोन्मुख विस्तार उपयोगी है

दोनों अनुप्रयोगों में, function g(x) के भीतर प्रदर्शित हो रहा है O(·) को आम तौर पर यथासंभव सरल चुना जाता है, निरंतर कारकों और निचले क्रम की शर्तों को छोड़ दिया जाता है।

इस नोटेशन के दो औपचारिक रूप से करीब, लेकिन स्पष्ट रूप से भिन्न उपयोग हैं:

• अनंत स्पर्शोन्मुखता
• बहुत छोता एसिम्प्टोटिक्स।

यह अंतर केवल अनुप्रयोग में है और सिद्धांत रूप में नहीं, हालांकि - बड़े O के लिए औपचारिक परिभाषा दोनों मामलों के लिए समान है, केवल फ़ंक्शन तर्क के लिए अलग-अलग सीमाएं हैं।Template:Or inline

अनंत स्पर्शोन्मुख

File:Comparison computational complexity.svg

एल्गोरिदम के विश्लेषण में आमतौर पर उपयोग किए जाने वाले फ़ंक्शन के ग्राफ़, संचालन की संख्या दर्शाते हैं N बनाम इनपुट आकार nप्रत्येक फ़ंक्शन के लिए

दक्षता के लिए एल्गोरिदम का विश्लेषण करते समय बिग ओ नोटेशन उपयोगी होता है। उदाहरण के लिए, आकार की समस्या को पूरा करने में लगने वाला समय (या चरणों की संख्या)। n पाया जा सकता है T(n) = 4n² − 2n + 2. जैसा n बड़ा हो जाता है, n² सारांश हावी हो जाएगा, ताकि अन्य सभी शर्तों की उपेक्षा की जा सके - उदाहरण के लिए जब n = 500, शब्द 4n² से 1000 गुना बड़ा है 2n अवधि। उत्तरार्द्ध को अनदेखा करने से अधिकांश उद्देश्यों के लिए अभिव्यक्ति के मूल्य पर नगण्य प्रभाव पड़ेगा। इसके अलावा, यदि हम अभिव्यक्ति के सन्निकटन के किसी अन्य आदेश से तुलना करते हैं, जैसे कि पद युक्त अभिव्यक्ति, तो गुणांक अप्रासंगिक हो जाते हैं n³ या n⁴. भले ही T(n) = 1,000,000n², अगर U(n) = n³, बाद वाला हमेशा पहले वाले से बार अधिक होगा n से बड़ा हो जाता है 1,000,000 (T(1,000,000) = 1,000,000³ = U(1,000,000)). इसके अतिरिक्त, चरणों की संख्या मशीन मॉडल के विवरण पर निर्भर करती है जिस पर एल्गोरिदम चलता है, लेकिन विभिन्न प्रकार की मशीनें आमतौर पर एल्गोरिदम को निष्पादित करने के लिए आवश्यक चरणों की संख्या में केवल स्थिर कारक से भिन्न होती हैं। तो बड़ा O नोटेशन जो बचता है उसे पकड़ लेता है: हम या तो लिखते हैं

$T(n)=O(n^{2})$

या

$T(n)\in O(n^{2})$

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

अनंतिम स्पर्शोन्मुखता

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

${\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\[4pt]&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\[4pt]&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}$

दूसरा व्यंजक (O(x वाला)।³)) का अर्थ है त्रुटि e का निरपेक्ष मान^x − (1 + x + x²/2) अधिक से अधिक कुछ स्थिर समय है |एक्स³| जब x 0 के काफी करीब हो।

गुण

यदि फ़ंक्शन f को अन्य कार्यों के सीमित योग के रूप में लिखा जा सकता है, फिर सबसे तेजी से बढ़ने वाला क्रम निर्धारित करता है f(n). उदाहरण के लिए,

$f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .$

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

हम किसी भी शक्ति को नजरअंदाज कर सकते हैं n लघुगणक के अंदर। सेट O(log n) बिलकुल वैसा ही है O(log(n^c)). लघुगणक केवल स्थिर कारक से भिन्न होते हैं (क्योंकि log(n^c) = c log n) और इस प्रकार बड़ा O नोटेशन इसे अनदेखा कर देता है। इसी प्रकार, विभिन्न स्थिर आधारों वाले लॉग समतुल्य होते हैं। दूसरी ओर, विभिन्न आधारों वाले घातांक ही क्रम के नहीं होते हैं। उदाहरण के लिए, 2ⁿ और 3ⁿ समान क्रम के नहीं हैं।

बदलती इकाइयाँ परिणामी एल्गोरिदम के क्रम को प्रभावित कर भी सकती हैं और नहीं भी। इकाइयों को बदलना, जहां कहीं भी दिखाई दे, उचित चर को स्थिरांक से गुणा करने के बराबर है। उदाहरण के लिए, यदि कोई एल्गोरिदम क्रम में चलता है n², प्रतिस्थापित करना n द्वारा cn का अर्थ है कि एल्गोरिदम क्रम में चलता है c²n², और बड़ा O अंकन स्थिरांक को अनदेखा करता है c². इसे ऐसे लिखा जा सकता है c²n² = O(n²). यदि, तथापि, एल्गोरिथ्म के क्रम में चलता है 2ⁿ, प्रतिस्थापित करना n साथ cn देता है 2^cn = (2^c)ⁿ. यह इसके बराबर नहीं है 2ⁿ सामान्य रूप में। चर बदलने से परिणामी एल्गोरिदम का क्रम भी प्रभावित हो सकता है। उदाहरण के लिए, यदि किसी एल्गोरिदम का रन टाइम है O(n) जब संख्या के संदर्भ में मापा जाता है n किसी इनपुट संख्या के अंकों का x, तो इसका रन टाइम है O(log x) जब इनपुट संख्या के फ़ंक्शन के रूप में मापा जाता है xस्वयं, क्योंकि n = O(log x).

उत्पाद

$f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})$

$f\cdot O(g)=O(fg)$

योग

अगर $f_{1}=O(g_{1})$ और $f_{2}=O(g_{2})$ तब $f_{1}+f_{2}=O(\max(g_{1},g_{2}))$. यह इस प्रकार है कि यदि $f_{1}=O(g)$ और $f_{2}=O(g)$ तब $f_{1}+f_{2}\in O(g)$. दूसरे शब्दों में, यह दूसरा कथन यही कहता है $O(g)$ उत्तल शंकु है.

एक स्थिरांक से गुणा

होने देना k शून्येतर स्थिरांक हो। तब $O(|k|\cdot g)=O(g)$. दूसरे शब्दों में, यदि $f=O(g)$, तब $k\cdot f=O(g).$

एकाधिक चर

बिग ओ (और छोटे ओ, Ω, आदि) का उपयोग कई वेरिएबल्स के साथ भी किया जा सकता है। कई चरों के लिए बड़े O को औपचारिक रूप से परिभाषित करने के लिए, मान लीजिए $f$ और $g$ के कुछ उपसमुच्चय पर परिभाषित दो कार्य हैं $\mathbb {R} ^{n}$. हम कहते हैं

$f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty$

यदि और केवल यदि स्थिरांक मौजूद हैं $M$ और $C>0$ ऐसा है कि $|f(\mathbf {x} )|\leq C|g(\mathbf {x} )|$ सभी के लिए $\mathbf {x}$ साथ $x_{i}\geq M$ कुछ के लिए $i.$ समान रूप से, शर्त यह है कि $x_{i}\geq M$ कुछ के लिए $i$ लिखा जा सकता है $\|\mathbf {x} \|_{\infty }\geq M$, कहाँ $\|\mathbf {x} \|_{\infty }$ चेबीशेव मानदंड को दर्शाता है। उदाहरण के लिए, कथन

$f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty$

दावा करता है कि ऐसे स्थिरांक C और M मौजूद हैं

$|f(n,m)-(n^{2}+m^{3})|\leq C|n+m|$

जब भी या तो $m\geq M$ या $n\geq M$ धारण करता है. यह परिभाषा सभी निर्देशांकों की अनुमति देती है $\mathbf {x}$ अनंत तक बढ़ना. विशेष रूप से, कथन

$f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty$

(अर्थात।, $\exists C\,\exists M\,\forall n\,\forall m\,\cdots$) से काफी अलग है

$\forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty$

(अर्थात।, $\forall m\,\exists C\,\exists M\,\forall n\,\cdots$).

इस परिभाषा के तहत, उपसमुच्चय जिस पर फ़ंक्शन परिभाषित किया गया है, यूनीवेरिएट सेटिंग से मल्टीवेरिएट सेटिंग में कथनों को सामान्यीकृत करते समय महत्वपूर्ण होता है। उदाहरण के लिए, यदि $f(n,m)=1$ और $g(n,m)=n$, तब $f(n,m)=O(g(n,m))$ अगर हम प्रतिबंधित करते हैं $f$ और $g$ को $[1,\infty )^{2}$, लेकिन तब नहीं जब उन्हें परिभाषित किया गया हो $[0,\infty )^{2}$.

बहुभिन्नरूपी कार्यों के लिए बड़े O का यह एकमात्र सामान्यीकरण नहीं है, और व्यवहार में, परिभाषा के चुनाव में कुछ असंगतता है।

अंकन के मामले

बराबर का चिह्न

कथन f(x) O(g(x)) है जैसा कि ऊपर परिभाषित किया गया है, आमतौर पर इस प्रकार लिखा जाता है f(x) = O(g(x)). कुछ लोग इसे संकेतन का दुरुपयोग मानते हैं, क्योंकि बराबर चिह्न का उपयोग भ्रामक हो सकता है क्योंकि यह समरूपता का सुझाव देता है जो इस कथन में नहीं है। जैसा कि निकोलस गोवर्ट डी ब्रुइज़न कहते हैं, O(x) = O(x²) सत्य है लेकिन O(x²) = O(x) क्या नहीं है। डोनाल्ड नुथ ऐसे बयानों को एकतरफा समानता के रूप में वर्णित करते हैं, क्योंकि यदि पक्षों को उलटा किया जा सकता है, तो हम हास्यास्पद बातें निकाल सकते हैं n = n²पहचान से n = O(n²) और n² = O(n²). अन्य पत्र में, नथ ने यह भी बताया कि समानता चिह्न ऐसे अंकन के संबंध में सममित नहीं है, क्योंकि, इस अंकन में, गणितज्ञ परंपरागत रूप से = चिह्न का उपयोग करते हैं क्योंकि वे अंग्रेजी में शब्द का उपयोग करते हैं: अरस्तू आदमी है, लेकिन आदमी है जरूरी नहीं कि अरस्तू हो। इन कारणों से, संकेतन सेट करें का उपयोग करना और लिखना अधिक सटीक होगा f(x) ∈ O(g(x)) (इस प्रकार पढ़ें: f(x) तत्व (गणित)#नोटेशन और शब्दावली O(g(x)) , या f(x) सेट O(g(x)) में है), O(g(x) के बारे में सोचते हुए )) सभी कार्यों का वर्ग h(x) इस प्रकार है कि |h(x)| ≤ कुछ सकारात्मक वास्तविक संख्या C के लिए Cg(x)।हालाँकि, बराबर चिह्न का उपयोग प्रथागत है।

अन्य अंकगणितीय ऑपरेटर

बिग ओ नोटेशन का उपयोग अधिक जटिल समीकरणों में अन्य अंकगणितीय ऑपरेटरों के साथ संयोजन में भी किया जा सकता है। उदाहरण के लिए, h(x) + O(f(x)) h(x) की वृद्धि के साथ-साथ भाग वाले कार्यों के संग्रह को दर्शाता है जिसकी वृद्धि f(x) तक सीमित है। इस प्रकार,

$g(x)=h(x)+O(f(x))$

के समान ही व्यक्त करता है

$g(x)-h(x)=O(f(x)).$

उदाहरण

मान लीजिए कि n तत्वों के सेट पर काम करने के लिए कलन विधि विकसित किया जा रहा है। इसके डेवलपर्स फ़ंक्शन T(n) खोजने में रुचि रखते हैं जो यह व्यक्त करेगा कि इनपुट सेट में तत्वों की संख्या के संदर्भ में एल्गोरिदम को चलने में कितना समय लगेगा (समय के कुछ मनमाने माप में)। एल्गोरिदम सेट में तत्वों को क्रमबद्ध करने के लिए पहले सबरूटीन को कॉल करके काम करता है और फिर अपने स्वयं के संचालन करता है। इस प्रकार में O(n) की ज्ञात समय जटिलता है²), और सबरूटीन चलने के बाद एल्गोरिदम को अतिरिक्त लेना होगा 55n³ + 2n + 10 समाप्त होने से पहले के चरण। इस प्रकार एल्गोरिथ्म की समग्र समय जटिलता को इस प्रकार व्यक्त किया जा सकता है T(n) = 55n³ + O(n²). यहाँ शर्तें 2n + 10 तेजी से बढ़ने वाले O(n) में समाहित हो गए हैं²). फिर, यह उपयोग = प्रतीक के कुछ औपचारिक अर्थों की उपेक्षा करता है, लेकिन यह प्रकार के सुविधाजनक प्लेसहोल्डर के रूप में बड़े ओ नोटेशन का उपयोग करने की अनुमति देता है।

एकाधिक उपयोग

अधिक जटिल उपयोग में, O(·) समीकरण में विभिन्न स्थानों पर प्रकट हो सकता है, यहाँ तक कि प्रत्येक पक्ष पर कई बार भी। उदाहरण के लिए, निम्नलिखित सत्य हैं $n\to \infty$:

$${\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}$$

ऐसे कथनों का अर्थ इस प्रकार है: किसी भी फ़ंक्शन के लिए जो बाईं ओर प्रत्येक O(·) को संतुष्ट करता है, दाईं ओर प्रत्येक O(·) को संतुष्ट करने वाले कुछ फ़ंक्शन हैं, जैसे कि इन सभी कार्यों को समीकरण में प्रतिस्थापित करना बनता है दो पक्ष बराबर. उदाहरण के लिए, उपरोक्त तीसरे समीकरण का अर्थ है: किसी भी फ़ंक्शन f(n) = O(1) के लिए, कुछ फ़ंक्शन g(n) = O(e) हैⁿ) ऐसा कि n^f(n) = g(n). उपरोक्त सेट नोटेशन के संदर्भ में, अर्थ यह है कि बाईं ओर द्वारा दर्शाए गए कार्यों का वर्ग दाईं ओर द्वारा दर्शाए गए कार्यों के वर्ग का उपसमूह है। इस प्रयोग में = औपचारिक प्रतीक है जो = के सामान्य प्रयोग के विपरीत सममित संबंध नहीं है। इस प्रकार उदाहरण के लिए n^O(1) = O(eⁿ) गलत बयान का संकेत नहीं देता O(eⁿ) = n^O(1).

टाइपसेटिंग

बिग O को इटैलिकाइज़्ड अपरकेस O के रूप में टाइप किया गया है, जैसा कि निम्नलिखित उदाहरण में है: $O(n^{2})$. TeX में, यह केवल गणित मोड के अंदर O टाइप करके निर्मित होता है। ग्रीक-नामांकित बैचमैन-लैंडौ नोटेशन के विपरीत, इसे किसी विशेष प्रतीक की आवश्यकता नहीं है। फिर भी, कुछ लेखक सुलेख संस्करण का उपयोग करते हैं ${\mathcal {O}}$ बजाय।

सामान्य कार्यों के क्रम

Further information: Time complexity § Table of common time complexities

यहां उन फ़ंक्शंस के वर्गों की सूची दी गई है जो आमतौर पर एल्गोरिदम के चलने के समय का विश्लेषण करते समय सामने आते हैं। प्रत्येक मामले में, c धनात्मक स्थिरांक है और n बिना किसी सीमा के बढ़ता है। धीमी गति से बढ़ने वाले कार्यों को आम तौर पर पहले सूचीबद्ध किया जाता है।

Notation	Name	Example
$O(1)$	constant	Determining if a binary number is even or odd; Calculating $(-1)^{n}$; Using a constant-size lookup table
$O(\log \log n)$	double logarithmic	Average number of comparisons spent finding an item using interpolation search in a sorted array of uniformly distributed values
$O(\log n)$	logarithmic	Finding an item in a sorted array with a binary search or a balanced search tree as well as all operations in a binomial heap
$O((\log n)^{c})$ ${\textstyle c>1}$	polylogarithmic	Matrix chain ordering can be solved in polylogarithmic time on a parallel random-access machine.
$O(n^{c})$ ${\textstyle 0<c<1}$	fractional power	Searching in a k-d tree
$O(n)$	linear	Finding an item in an unsorted list or in an unsorted array; adding two n-bit integers by ripple carry
$O(n\log ^{*}n)$	n log-star n	Performing triangulation of a simple polygon using Seidel's algorithm, or the union–find algorithm. Note that $\log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}$
$O(n\log n)=O(\log n!)$	linearithmic, loglinear, quasilinear, or "n log n"	Performing a fast Fourier transform; fastest possible comparison sort; heapsort and merge sort
$O(n^{2})$	quadratic	Multiplying two n-digit numbers by 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
$O(n^{c})$	polynomial or algebraic	Tree-adjoining grammar parsing; maximum matching for bipartite graphs; finding the determinant with LU decomposition
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ ${\textstyle 0<\alpha <1}$	L-notation or sub-exponential	Factoring a number using the quadratic sieve or number field sieve
$O(c^{n})$ ${\textstyle c>1}$	exponential	Finding the (exact) solution to the travelling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute-force search
$O(n!)$	factorial	Solving the travelling salesman problem via brute-force search; generating all unrestricted permutations of a poset; finding the determinant with Laplace expansion; enumerating all partitions of a set

कथन $f(n)=O(n!)$ कभी-कभी कमजोर हो जाता है $f(n)=O\left(n^{n}\right)$ स्पर्शोन्मुख जटिलता के लिए सरल सूत्र प्राप्त करना। किसी के लिए $k>0$ और $c>0$, $O(n^{c}(\log n)^{k})$ का उपसमुच्चय है $O(n^{c+\varepsilon })$ किसी के लिए $\varepsilon >0$, इसलिए इसे किसी बड़े क्रम वाला बहुपद माना जा सकता है।

संबंधित स्पर्शोन्मुख संकेतन

कंप्यूटर विज्ञान में बिग ओ का व्यापक रूप से उपयोग किया जाता है। कुछ अन्य संबंधित नोटेशनों के साथ, यह बैचमैन-लैंडौ नोटेशन के परिवार का निर्माण करता है।

लिटिल-ओ नोटेशन

"Little o" redirects here. For the baseball player, see Omar Vizquel.

सहज रूप से, दावाf(x) है o(g(x)) (पढ़नाf(x) छोटा-ओ का है g(x) ) मतलब कि g(x) की तुलना में बहुत तेजी से बढ़ता है f(x). पहले की तरह, मान लीजिए कि f वास्तविक या जटिल मान वाला फ़ंक्शन है और g वास्तविक मान वाला फ़ंक्शन है, दोनों को सकारात्मक वास्तविक संख्याओं के कुछ असीमित उपसमुच्चय पर परिभाषित किया गया है, जैसे कि x के सभी बड़े पर्याप्त मानों के लिए g(x) सख्ती से सकारात्मक है। लिखता है

$f(x)=o(g(x))\quad {\text{ as }}x\to \infty$

यदि प्रत्येक सकारात्मक स्थिरांक के लिए ε वहां स्थिरांक मौजूद है $x_{0}$ ऐसा है कि

$|f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.$

उदाहरण के लिए, किसी के पास है

$2x=o(x^{2})$ और $1/x=o(1),$ दोनों जैसे $x\to \infty .$

1. औपचारिक परिभाषा|बिग-ओ संकेतन की परिभाषा और छोटे-ओ की परिभाषा के बीच अंतर यह है कि जहां पूर्व को कम से कम स्थिरांक एम के लिए सत्य होना चाहिए, वहीं बाद वाले को प्रत्येक सकारात्मक स्थिरांक के लिए मान्य होना चाहिए ε, हालाँकि छोटा। इस तरह, लिटिल-ओ नोटेशन संबंधित बिग-ओ नोटेशन की तुलना में मजबूत कथन बनाता है: प्रत्येक फ़ंक्शन जो कि जी का छोटा-ओ है, वह भी जी का बड़ा-ओ है, लेकिन प्रत्येक फ़ंक्शन जो जी का बड़ा-ओ है वह भी नहीं है जी का छोटा-ओ. उदाहरण के लिए, $2x^{2}=O(x^{2})$ लेकिन $2x^{2}\neq o(x^{2})$.

चूँकि g(x) अशून्य है, या कम से कम निश्चित बिंदु से परे अशून्य हो जाता है, संबंध $f(x)=o(g(x))$ के बराबर है

$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0$ (और वास्तव में लैंडौ ऐसा ही हैमूल रूप से लिटिल-ओ नोटेशन को परिभाषित किया गया था)।

लिटिल-ओ कई अंकगणितीय संक्रियाओं का सम्मान करता है। उदाहरण के लिए,

अगर c शून्येतर स्थिरांक है और $f=o(g)$ तब $c\cdot f=o(g)$, और

अगर $f=o(F)$ और $g=o(G)$ तब $f\cdot g=o(F\cdot G).$

यह सकर्मक संबंध संबंध को भी संतुष्ट करता है:

अगर $f=o(g)$ और $g=o(h)$ तब $f=o(h).$

बिग ओमेगा संकेतन

एक अन्य स्पर्शोन्मुख संकेतन है $\Omega$, बिग ओमेगा पढ़ें। कथन की दो व्यापक और असंगत परिभाषाएँ हैं

$f(x)=\Omega (g(x))$ जैसा $x\to a$,

जहां a कुछ वास्तविक संख्या है, ∞, या −∞, जहां f और g, a के पड़ोस में परिभाषित वास्तविक कार्य हैं, और जहां g इस पड़ोस में सकारात्मक है।

हार्डी-लिटलवुड परिभाषा का उपयोग मुख्य रूप से विश्लेषणात्मक संख्या सिद्धांत में किया जाता है, और नुथ परिभाषा का उपयोग मुख्य रूप से कम्प्यूटेशनल जटिलता सिद्धांत में किया जाता है; परिभाषाएँ समतुल्य नहीं हैं.

हार्डी-लिटलवुड परिभाषा

1914 में गॉडफ्रे हेरोल्ड हार्डी और जॉन एडेंसर लिटिलवुड ने नया प्रतीक पेश किया $\Omega$, जिसे इस प्रकार परिभाषित किया गया है:

$f(x)=\Omega (g(x))$ जैसा $x\to \infty$ अगर $\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.$

इस प्रकार $f(x)=\Omega (g(x))$ का निषेध है $f(x)=o(g(x))$.

1916 में उन्हीं लेखकों ने दो नये प्रतीक प्रस्तुत किये $\Omega _{R}$ और $\Omega _{L}$, के रूप में परिभाषित:

$f(x)=\Omega _{R}(g(x))$ जैसा $x\to \infty$ अगर $\limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0$;

$f(x)=\Omega _{L}(g(x))$ जैसा $x\to \infty$ अगर $\liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.$

इन प्रतीकों का प्रयोग 1924 में एडमंड लैंडौ द्वारा इन्हीं अर्थों में किया गया था। लांडौ के बाद, नोटेशन का दोबारा कभी भी सटीक रूप से उपयोग नहीं किया गया; $\Omega _{R}$ बन गया $\Omega _{+}$ और $\Omega _{L}$ बन गया $\Omega _{-}$.

ये तीन प्रतीक $\Omega ,\Omega _{+},\Omega _{-}$, साथ ही $f(x)=\Omega _{\pm }(g(x))$ (मतलब है कि $f(x)=\Omega _{+}(g(x))$ और $f(x)=\Omega _{-}(g(x))$ दोनों संतुष्ट हैं), अब वर्तमान में विश्लेषणात्मक संख्या सिद्धांत में उपयोग किया जाता है।

सरल उदाहरण

अपने पास

$\sin x=\Omega (1)$ जैसा $x\to \infty ,$

और अधिक सटीक रूप से

$\sin x=\Omega _{\pm }(1)$ जैसा $x\to \infty .$

अपने पास

$\sin x+1=\Omega (1)$ जैसा $x\to \infty ,$

और अधिक सटीक रूप से

$\sin x+1=\Omega _{+}(1)$ जैसा $x\to \infty ;$

हालाँकि

$\sin x+1\not =\Omega _{-}(1)$ जैसा $x\to \infty .$

नथ परिभाषा

1976 में डोनाल्ड नथ ने अपने उपयोग को उचित ठहराने के लिए पेपर प्रकाशित किया $\Omega$-एक मजबूत संपत्ति का वर्णन करने के लिए प्रतीक।नुथ ने लिखा: कंप्यूटर विज्ञान में अब तक मैंने जितने भी अनुप्रयोग देखे हैं, उनके लिए मजबूत आवश्यकता... कहीं अधिक उपयुक्त है। उन्होंने परिभाषित किया

$f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))$

टिप्पणी के साथ: हालाँकि मैंने हार्डी और लिटिलवुड की परिभाषा बदल दी है $\Omega$, मुझे ऐसा करना उचित लगता है क्योंकि उनकी परिभाषा किसी भी तरह से व्यापक उपयोग में नहीं है, और क्योंकि तुलनात्मक रूप से दुर्लभ मामलों में जब उनकी परिभाषा लागू होती है तो वे जो कहना चाहते हैं उसे कहने के अन्य तरीके भी हैं।

बैचमैन-लैंडौ नोटेशन का परिवार

Notation	Name	Description	Formal definition	Limit definition
$f(n)=o(g(n))$	Small O; Small Oh	f is dominated by g asymptotically	$\forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|<k\,g(n)$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0$
$f(n)=O(g(n))$	Big O; Big Oh; Big Omicron	$|f|$ is bounded above by g (up to constant factor) asymptotically	$\exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)$	$\limsup _{n\to \infty }{\frac {f(n)}{g(n)}}<\infty$
$f(n)=\Theta (g(n))$	Big Theta	f is bounded both above and below by g asymptotically	$\exists k_{1}>0\,\exists k_{2}>0\,\exists n_{0}\,\forall n>n_{0}\colon$ $k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)$	$f(n)=O(g(n))$ and $f(n)=\Omega (g(n))$ (Knuth version)
$f(n)\sim g(n)$	On the order of	f is equal to g asymptotically	$\forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1$
$f(n)=\Omega (g(n))$	Big Omega in complexity theory (Knuth)	f is bounded below by g asymptotically	$\exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)\geq k\,g(n)$	$\liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0$
$f(n)=\omega (g(n))$	Small Omega	f dominates g asymptotically	$\forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)$	$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=\infty$
$f(n)=\Omega (g(n))$	Big Omega in number theory (Hardy–Littlewood)	$|f|$ is not dominated by g asymptotically	$\exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)$	Failed to parse (Conversion error. Server ("cli") reported: "SyntaxError: Expected "-", "[", "\\", "\\begin", "\\begin{", "]", "^", "_", "{", "}", [ \t\n\r], [%$], [().], [,:;?!'], [/|], [0-9], [><~], [\-+*=], or [a-zA-Z] but "ग" found.in 1:76"): {\displaystyle \limsup_{n \to \infty} \frac{\left|f(n)\right|}{g(n)} > 0 </गणित> |} सीमा परिभाषाएँ मानती हैं पर्याप्त रूप से बड़े के लिए गणित>जी(एन) > 0</गणित> गणित>एन</गणित>. तालिका को (आंशिक रूप से) इस अर्थ में सबसे छोटे से सबसे बड़े तक क्रमबद्ध किया गया है <math>o,O,\Theta,\sim, } (नुथ का संस्करण) $\Omega ,\omega$ कार्यों पर अनुरूप हैं $<,\leq ,\approx ,=,$$\geq ,>$ असली लाइन पर(हार्डी-लिटलवुड संस्करण $\Omega$हालाँकि, ऐसे किसी भी विवरण के अनुरूप नहीं है)। कंप्यूटर विज्ञान बड़ा उपयोग करता है $O$, बड़ी थीटा $\Theta$, थोड़ा $o$, थोड़ा ओमेगा $\omega$ और नुथ का बड़ा ओमेगा $\Omega$ संकेतन. विश्लेषणात्मक संख्या सिद्धांत अक्सर बड़े का उपयोग करता है $O$, छोटा $o$, हार्डी-लिटलवुड का बड़ा ओमेगा $\Omega$ (+, − या ± सबस्क्रिप्ट के साथ या उसके बिना) और $\sim$ संकेतन.छोटा ओमेगा $\omega$ विश्लेषण में अंकन का प्रयोग उतनी बार नहीं किया जाता है। कंप्यूटर विज्ञान में उपयोग Further information: Analysis of algorithms अनौपचारिक रूप से, विशेष रूप से कंप्यूटर विज्ञान में, बड़े ओ नोटेशन का उपयोग अक्सर एसिम्प्टोटिक ऊपरी और निचले सीमा # तंग सीमा का वर्णन करने के लिए कुछ अलग तरीके से किया जा सकता है, जहां बड़े थीटा Θ नोटेशन का उपयोग किसी दिए गए संदर्भ में तथ्यात्मक रूप से अधिक उपयुक्त हो सकता है। उदाहरण के लिए, किसी फ़ंक्शन T(n) = 73n पर विचार करते समय3+22एन2 + 58, निम्नलिखित में से सभी आम तौर पर स्वीकार्य हैं, लेकिन कड़ी सीमाएं (जैसे नीचे संख्या 2 और 3) आमतौर पर ढीली सीमाओं (जैसे नीचे संख्या 1) की तुलना में दृढ़ता से पसंद की जाती हैं। T(n) = O(n100) T(n) = O(n3) T(n) = Θ(n3) समतुल्य अंग्रेजी कथन क्रमशः हैं: T(n) बिना किसी लक्षण के n से अधिक तेजी से बढ़ता है100 T(n) बिना किसी लक्षण के n से अधिक तेजी से बढ़ता है3 T(n) n जितनी तेजी से लक्षणहीन रूप से बढ़ता है3. इसलिए जबकि तीनों कथन सत्य हैं, प्रत्येक में उत्तरोत्तर अधिक जानकारी समाहित है। हालाँकि, कुछ क्षेत्रों में, बड़े ओ नोटेशन (उपरोक्त सूचियों में नंबर 2) का उपयोग बड़े थीटा नोटेशन (उपरोक्त सूचियों में आइटम नंबर 3) की तुलना में अधिक सामान्यतः किया जाएगा। उदाहरण के लिए, यदि टी (एन) इनपुट आकार एन के लिए नए विकसित एल्गोरिदम के चलने के समय का प्रतिनिधित्व करता है, तो एल्गोरिदम के आविष्कारक और उपयोगकर्ता ऊपरी एसिम्प्टोटिक बाउंड लगाने के इच्छुक हो सकते हैं कि इसे चलाने में कितना समय लगेगा। निचली स्पर्शोन्मुख सीमा के बारे में स्पष्ट कथन। अन्य संकेतन अपनी पुस्तक एल्गोरिदम का परिचय में, थॉमस एच. कॉर्मेन, चार्ल्स ई. लेइसर्सन, रोनाल्ड एल. रिवेस्ट और क्लिफोर्ड स्टीन ने फ़ंक्शंस के सेट पर विचार किया है जो संतुष्ट करता है $f(n)=O(g(n))\quad (n\to \infty )~.$ उदाहरण के लिए, सही संकेतन में इस सेट को O(g) कहा जा सकता है, जहाँ $$O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.$$ लेखकों का कहना है कि सेट सदस्यता ऑपरेटर (∈) के बजाय सेट सदस्यता को दर्शाने के लिए समानता ऑपरेटर (=) का उपयोग नोटेशन का दुरुपयोग है, लेकिन ऐसा करने के फायदे हैं। किसी समीकरण या असमानता के अंदर, एसिम्प्टोटिक नोटेशन का उपयोग सेट ओ (जी) में अज्ञात फ़ंक्शन के लिए होता है, जो निम्न-क्रम वाले शब्दों को समाप्त करता है, और समीकरणों में अनावश्यक अव्यवस्था को कम करने में मदद करता है, उदाहरण के लिए: $2n^{2}+3n+1=2n^{2}+O(n).$ बाचमैन-लैंडौ नोटेशन का विस्तार कंप्यूटर विज्ञान में कभी-कभी उपयोग किया जाने वाला अन्य संकेतन Õ (सॉफ्ट-ओ पढ़ें) है, जो पॉलीलॉगरिदमिक कारकों को छुपाता है। उपयोग में दो परिभाषाएँ हैं: कुछ लेखक f(n)=Õ(g(n)) को आशुलिपि के रूप में उपयोग करते हैं f(n) = O(g(n) logk n) कुछ k के लिए, जबकि अन्य इसे शॉर्टहैंड के रूप में उपयोग करते हैं f(n) = O(g(n) logk g(n)). कब g(n) n में बहुपद है, कोई अंतर नहीं है; हालाँकि, बाद वाली परिभाषा किसी को यह कहने की अनुमति देती है, उदाहरण के लिए वह $n2^{n}={\tilde {O}}(2^{n})$ जबकि पूर्व परिभाषा इसकी अनुमति देती है $\log ^{k}n={\tilde {O}}(1)$ किसी स्थिरांक k के लिए। कुछ लेखक ओ लिखते हैं*बाद वाली परिभाषा के समान उद्देश्य के लिए। अनिवार्य रूप से, यह बड़ा ओ नोटेशन है, पॉलीलॉगरिदमिक फ़ंक्शन को अनदेखा कर रहा है क्योंकि एसिम्प्टोटिक विश्लेषण | कुछ अन्य सुपर-लघुगणकीय फ़ंक्शन के विकास-दर प्रभाव बड़े आकार के इनपुट पैरामीटर के लिए विकास-दर विस्फोट का संकेत देते हैं जो खराब रन-टाइम प्रदर्शन की भविष्यवाणी करने के लिए अधिक महत्वपूर्ण है लघुगणक-विकास कारक(ओं) द्वारा योगदान किए गए बेहतर-बिंदु प्रभावों की तुलना में। इस संकेतन का उपयोग अक्सर विकास-दर के भीतर होने वाली खामियों को दूर करने के लिए किया जाता है, जिन्हें मौजूदा मामलों के लिए बहुत कसकर बांधा गया है (लॉग के बाद से)kn हमेशा o(n) होता हैε) किसी भी स्थिरांक k और किसी के लिए ε > 0). इसके अलावा एल-नोटेशन, के रूप में परिभाषित किया गया है $L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ उन कार्यों के लिए सुविधाजनक है जो समय जटिलता#बहुपद समय और समय जटिलता#घातीय समय के बीच हैं $\ln n$. सामान्यीकरण और संबंधित उपयोग किसी भी मानक वेक्टर स्थान में मान लेने वाले कार्यों का सामान्यीकरण सीधा है (मानदंडों द्वारा निरपेक्ष मानों को प्रतिस्थापित करना), जहां एफ और जी को ही स्थान में अपने मान लेने की आवश्यकता नहीं है। किसी भी टोपोलॉजिकल समूह में मान लेने वाले कार्यों का सामान्यीकरण भी संभव है. सीमित प्रक्रिया x → xo मनमाना फ़िल्टर आधार, यानी निर्देशित नेट (गणित) एफ और जी को पेश करके भी सामान्यीकृत किया जा सकता है। ओ नोटेशन का उपयोग काफी सामान्य स्थानों में यौगिक और भिन्नता को परिभाषित करने के लिए किया जा सकता है, और कार्यों की (स्पर्शोन्मुख) समतुल्यता को भी परिभाषित करने के लिए किया जा सकता है, $f\sim g\iff (f-g)\in o(g)$ जो कि तुल्यता संबंध है और संबंध f की तुलना में अधिक प्रतिबंधात्मक धारणा है, ऊपर से Θ(g) है। (यदि एफ और जी सकारात्मक वास्तविक मूल्य वाले फ़ंक्शन हैं तो यह लिम एफ/जी = 1 तक कम हो जाता है।) उदाहरण के लिए, 2x Θ(x) है, लेकिन 2x − x ओ(एक्स) नहीं है। इतिहास (बाचमन-लैंडौ, हार्डी, और विनोग्राडोव नोटेशन) प्रतीक O को पहली बार संख्या सिद्धांतकार पॉल बैचमैन ने 1894 में अपनी पुस्तक एनालिटिशे ज़हलेनथियोरी (विश्लेषणात्मक संख्या सिद्धांत) के दूसरे खंड में पेश किया था। संख्या सिद्धांतकार एडमंड लैंडौ ने इसे अपनाया, और इस प्रकार 1909 में अंकन ओ को पेश करने के लिए प्रेरित हुए; इसलिए दोनों को अब लैंडौ प्रतीक कहा जाता है। इन नोटेशनों का उपयोग 1950 के दशक के दौरान स्पर्शोन्मुख विश्लेषण के लिए अनुप्रयुक्त गणित में किया गया था। प्रतीक $\Omega$ (इस अर्थ में ओ का कोई मतलब नहीं है) 1914 में हार्डी और लिटिलवुड द्वारा पेश किया गया था।हार्डी और लिटिलवुड ने भी 1916 में प्रतीकों की शुरुआत की $\Omega _{R}$ (दाएं) और $\Omega _{L}$ ( बाएं ), आधुनिक प्रतीकों के अग्रदूत $\Omega _{+}$ (एक छोटे से ओ से छोटा नहीं है) और $\Omega _{-}$ (के छोटे से से बड़ा नहीं है). इस प्रकार ओमेगा प्रतीकों (उनके मूल अर्थ के साथ) को कभी-कभी लैंडौ प्रतीकों के रूप में भी जाना जाता है। यह संकेतन $\Omega$ कम से कम 1950 के दशक से संख्या सिद्धांत में इसका आमतौर पर उपयोग किया जाने लगा। 1970 के दशक में बिग ओ को डोनाल्ड नुथ द्वारा कंप्यूटर विज्ञान में लोकप्रिय बनाया गया, जिन्होंने संबंधित थीटा नोटेशन की शुरुआत की, और ओमेगा नोटेशन के लिए अलग परिभाषा प्रस्तावित की। लैंडौ ने कभी भी बड़े थीटा और छोटे ओमेगा प्रतीकों का उपयोग नहीं किया। हार्डी के प्रतीक थे (आधुनिक ओ अंकन के संदर्भ में) $f\preccurlyeq g\iff f\in O(g)$ और $f\prec g\iff f\in o(g);$ (हालांकि हार्डी ने कभी भी नोटेशन को परिभाषित या उपयोग नहीं किया $\prec \!\!\prec$, और न $\ll$, जैसा कि कभी-कभी रिपोर्ट किया गया है)। हार्डी ने प्रतीकों का परिचय दिया $\preccurlyeq$ और $\prec$ (साथ ही कुछ अन्य प्रतीकों) को उनके 1910 के ट्रैक्ट ऑर्डर्स ऑफ इन्फिनिटी में प्रकाशित किया गया था, और उनका उपयोग केवल तीन पत्रों (1910-1913) में किया गया था। अपने लगभग 400 शेष पत्रों और पुस्तकों में उन्होंने लगातार लैंडौ प्रतीकों ओ और ओ का उपयोग किया। हार्डी के नोटेशन का अब उपयोग नहीं किया जाता है। दूसरी ओर, 1930 के दशक में, रूसी संख्या सिद्धांतकार इवान मतवेयेविच विनोग्रादोव ने अपना अंकन प्रस्तुत किया$\ll$, जिसका उपयोग संख्या सिद्धांत के बजाय तेजी से किया जा रहा है $O$ अंकन. अपने पास $f\ll g\iff f\in O(g),$ और अक्सर दोनों नोटेशन का उपयोग ही पेपर में किया जाता है। बिग-ओ मूल रूप से ऑर्डर ऑफ (ऑर्डनंग, बैचमैन 1894) को दर्शाता है, और इस प्रकार यह लैटिन अक्षर है। न तो बैचमैन और न ही लैंडौ ने कभी इसे ऑमिक्रॉन कहा। इस प्रतीक को बहुत बाद में (1976) नुथ ने बड़े ओमीक्रॉन के रूप में देखा,संभवतः प्रतीक ओमेगा की उनकी परिभाषा के संदर्भ में। अंक 0 का प्रयोग नहीं किया जाना चाहिए. यह भी देखें स्पर्शोन्मुख विस्तार: टेलर के सूत्र को सामान्य बनाने वाले कार्यों का सन्निकटन एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम: वाक्यांश जो अक्सर एल्गोरिदम का वर्णन करने के लिए उपयोग किया जाता है जिसमें समस्या के लिए निचली सीमा के स्थिरांक के भीतर एसिम्प्टोटिक रूप से ऊपरी सीमा होती है संभाव्यता संकेतन में बड़ा O: Op, ओp* निम्न को सीमित करें और श्रेष्ठ को सीमित करें: इस आलेख में उपयोग किए गए कुछ सीमा संकेतन का स्पष्टीकरण मास्टर प्रमेय (एल्गोरिदम का विश्लेषण): बिग ओ नोटेशन का उपयोग करके विभाजित करें और जीतें पुनरावर्ती एल्गोरिदम का विश्लेषण करने के लिए नचबिन का प्रमेय: जटिल विश्लेषणात्मक कार्यों को सीमित करने की सटीक विधि ताकि अभिन्न परिवर्तनों के अभिसरण के क्षेत्र को बताया जा सके सन्निकटन का क्रम गणितीय संक्रियाओं की कम्प्यूटेशनल जटिलता सन्दर्भ और नोट्स अग्रिम पठन Hardy, G. H. (1910). Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond. Cambridge University Press. Knuth, Donald (1997). "1.2.11: Asymptotic Representations". Fundamental Algorithms. The Art of Computer Programming. Vol. 1 (3rd ed.). Addison-Wesley. ISBN 978-0-201-89683-1. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "3.1: Asymptotic notation". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. pp. 226–228. ISBN 978-0-534-94728-6. Avigad, Jeremy; Donnelly, Kevin (2004). Formalizing O notation in Isabelle/HOL (PDF). International Joint Conference on Automated Reasoning. doi:10.1007/978-3-540-25984-8_27. Black, Paul E. (11 March 2005). Black, Paul E. (ed.). "big-O notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006. Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "little-o notation". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006. Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "Ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006. Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "ω". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006. Black, Paul E. (17 December 2004). Black, Paul E. (ed.). "Θ". Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Retrieved December 16, 2006. बाहरी संबंध Growth of sequences — OEIS (Online Encyclopedia of Integer Sequences) Wiki Introduction to Asymptotic Notations Big-O Notation – What is it good for An example of Big O in accuracy of central divided difference scheme for first derivative Archived 2018-10-07 at the Wayback Machine A Gentle Introduction to Algorithm Complexity Analysis