बिग ओ अंकन

बिगओनोटेशन का उदाहरण: ${\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 संकेतन का उपयोग किया जाता है।

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

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

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

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

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

और इसे पढ़ते है "$f(x)$,$g(x)$ का बिग O है" यदि $x$ के सभी पर्याप्त बड़े मानों के लिए $f(x)$ का निरपेक्ष मान,$g(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$ उपस्थित हैं ऐसा कि $0<|x-a|<\delta$,के साथ सभी $x$ के लिए परिभाषित है

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

जैसा कि $x$ के कुछ मानों के लिए, $g(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⁴ है।अब कोई दूसरा नियम प्रयुक्त कर सकता है:6 और x⁴ का उत्पाद 6x⁴ है जिसमें पहला कारक x पर निर्भर नहीं करता है।इस कारक को छोड़ने से सरलीकृत रूप x⁴ में परिणाम मिलता है।इस प्रकार,हम कहते हैं कि f(x),x⁴का "बिग O" है।गणितीय रूप से, हम 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}.$$

उपयोग

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

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

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

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

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

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

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

एल्गोरिदम के विश्लेषण में सामान्यतः उपयोग किए जाने वाले फलन के ग्राफ़, संचालन की संख्या दर्शाते हैं 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² समय जटिलता. संकेत का अभिप्राय अपने सामान्य गणितीय अर्थ में सामान्य को व्यक्त करना नहीं है, किन्तु अधिक बोलचाल की भाषा है, इसलिए दूसरी अभिव्यक्ति को कभी-कभी अधिक स्पष्ट माना जाता है (नीचे सामान्य चिह्न चर्चा देखें) जबकि पहली को कुछ लोगों द्वारा दुरुपयोग माना जाता है .

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

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

${\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³| समय है जब 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) जब इनपुट संख्या के फलन के रूप में मापा जाता है

उत्पाद

$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, Ω, आदि) का उपयोग कई वेरिएबल्स के साथ भी किया जा सकता है। कई चरों के लिए बड़े 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$ कुछ $\|\mathbf {x} \|_{\infty }\geq M$ के लिए $i$ लिखा जा सकता है , जहाँ $\|\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(x2) सत्य है किन्तु O(x2) = O(x) नहीं है। डोनाल्ड नुथ ऐसे कथनों को "एकतरफ़ा समानता" के रूप में वर्णित करते हैं क्योंकि यदि पक्षों को उलटा किया जा सकता है, "हम पहचान n = O(n2) और n2 = O(n2) से n = n2 जैसी हास्यास्पद चीजें निकाल सकते हैं। एक अन्य पत्र में नथ ने यह भी बताया कि "समानता चिह्न ऐसे अंकन के संबंध में सममित नहीं है" जैसा कि इस अंकन में है "गणितज्ञ परंपरागत रूप से चिह्न का उपयोग करते हैं क्योंकि वे अंग्रेजी में "is" शब्द का उपयोग करते हैं: अरस्तू एक आदमी है किन्तु एक आदमी है आवश्यक नहीं कि अरस्तू ही हो"।

इन कारणों से सेट नोटेशन का उपयोग करना और 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 नोटेशन का उपयोग करने की अनुमति देता है।

एकाधिक उपयोग

अधिक जटिल उपयोग में,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(n^{2})$. टेक्स में, यह केवल गणित मोड के अंदर O टाइप करके निर्मित होता है। ग्रीक-नामांकित बैचमैन-लैंडौ नोटेशन के विपरीत, इसे किसी विशेष प्रतीक की आवश्यकता नहीं है। फिर भी, कुछ लेखक सुलेख संस्करण का उपयोग करते हैं ।

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

Further information: समय जटिलता § सामान्य समय जटिलताओं की तालिका

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

नोटेशन	नाम	उदहारण
$O(1)$	स्थिरांक	यह निर्धारित करना कि कोई बाइनरी संख्या सम है या विषम; स्थिरांक-आकार लुकअप तालिका का उपयोग करके (−1)𝑛 की गणना करना
$O(\log \log n)$	दोहरा लघुगणक	समान रूप से वितरित मूल्यों की क्रमबद्ध सरणी में इंटरपोलेशन खोज का उपयोग करके किसी आइटम को खोजने में खर्च की गई तुलनाओं की औसत संख्या
$O(\log n)$	लघुगणकीय	बाइनरी खोज या संतुलित खोज ट्री के साथ-साथ द्विपद ढेर में सभी परिचालनों के साथ क्रमबद्ध सरणी में एक आइटम ढूंढना
$O((\log n)^{c})$ ${\textstyle c>1}$	बहुगणितीय	मैट्रिक्स श्रृंखला क्रम को समानांतर रैंडम-एक्सेस मशीन पर बहुगणितीय समय में हल किया जा सकता है।
$O(n^{c})$ ${\textstyle 0<c<1}$	भिन्नात्मक शक्ति	के-डी वृक्ष में खोज रहा हूँ
$O(n)$	रेखीय	किसी अवर्गीकृत सूची में या किसी अवर्गीकृत सरणी में कोई आइटम ढूँढना; रिपल कैरी द्वारा दो n-बिट पूर्णांक जोड़ना
$O(n\log ^{*}n)$	n लॉग-स्टार n	सीडेल एल्गोरिथ्म, या संघ-खोज एल्गोरिथ्म का उपयोग करके एक साधारण बहुभुज का त्रिकोणासन करना। ध्यान दें कि$\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!)$	लीनियरिथ्मिक, लॉगलीनियर, क्वासिलिनियर, या "n लॉग n"	तेजी से फूरियर रूपांतरण निष्पादित करना; सबसे तेज़ संभव तुलना प्रकार; हीपसॉर्ट और मर्ज सॉर्ट
$O(n^{2})$	द्विघात	स्कूली पुस्तक गुणन द्वारा दो n-अंकीय संख्याओं को गुणा करना; सरल सॉर्टिंग एल्गोरिदम, जैसे बबल सॉर्ट, चयन सॉर्ट और इंसर्शन सॉर्ट; (सबसे खराब स्थिति) कुछ सामान्यतः तेज़ सॉर्टिंग एल्गोरिदम जैसे कि क्विकॉर्ट, शेलसॉर्ट और ट्री सॉर्ट पर बाध्य
$O(n^{c})$	बहुपद या बीजगणितीय	वृक्ष-आसन्न व्याकरण विश्लेषण; द्विदलीय ग्राफ़ के लिए अधिकतम मिलान; एलयू अपघटन के साथ निर्धारक का पता लगाना
$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$ ${\textstyle 0<\alpha <1}$	एल-नोटेशन या उप-घातांकीय	द्विघात छलनी या संख्या क्षेत्र छलनी का उपयोग करके किसी संख्या का गुणनखंड करना
$O(c^{n})$ ${\textstyle c>1}$	घातीय	गतिशील प्रोग्रामिंग का उपयोग करके ट्रैवलिंग सेल्समैन समस्या का (सटीक) समाधान ढूंढना; पाशविक-बल खोज का उपयोग करके यह निर्धारित करना कि क्या दो तार्किक कथन समतुल्य हैं
$O(n!)$	भाज्य	क्रूर-बल खोज के माध्यम से ट्रैवलिंग सेल्समैन की समस्या का समाधान; किसी पोसेट के सभी अप्रतिबंधित क्रमपरिवर्तन उत्पन्न करना; लाप्लास विस्तार के साथ निर्धारक का पता लगाना; एक सेट के सभी विभाजनों की गणना करना

कथन $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$, इसलिए इसे किसी बड़े क्रम वाला बहुपद माना जा सकता है।

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

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

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

"लिटिल ओ" redirects here. For बेसबॉल खिलाड़ी, see उमर विज़क्वेल.

सहज रूप से, प्रमाणित "f(x) o(g(x)) है" (पढ़ें "f(x) g(x) का छोटा-o है") का अर्थ है कि 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$ है , मुझे ऐसा करना उचित लगता है क्योंकि उनकी परिभाषा किसी भी तरह से व्यापक उपयोग में नहीं है, और क्योंकि तुलनात्मक रूप से दुर्लभ स्थितियों में जब उनकी परिभाषा प्रयुक्त होती है जिससे वे जो कहना चाहते हैं उसे कहने के अन्य विधि भी हैं।

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

सीमा परिभाषाएँ मानती हैं पर्याप्त रूप से बड़े के लिए गणित>जी(एन) $g(n)>0$. तालिका को (आंशिक रूप से) इस अर्थ में सबसे छोटे से सबसे बड़े तक क्रमबद्ध किया गया है $o,O,\Theta ,\sim$ (नुथ का संस्करण) $\Omega ,\omega$ फलनों पर अनुरूप हैं $<,\leq ,\approx ,=,$$\geq ,>$ असली लाइन पर (हार्डी-लिटलवुड संस्करण $\Omega$, चूँकि, ऐसे किसी भी विवरण के अनुरूप नहीं है)।

कंप्यूटर विज्ञान बड़ा उपयोग करता है $O$, बड़ी थीटा $\Theta$, थोड़ा $o$, थोड़ा ओमेगा $\omega$ और नुथ का बड़ा ओमेगा $\Omega$ संकेतन. विश्लेषणात्मक संख्या सिद्धांत अधिकांशतः बड़े का उपयोग करता है $O$, छोटा $o$, हार्डी-लिटलवुड का बड़ा ओमेगा $\Omega$ (+, − या ± सबस्क्रिप्ट के साथ या उसके बिना) और $\sim$ संकेतन. छोटा ओमेगा $\omega$ विश्लेषण में अंकन का प्रयोग उतनी बार नहीं किया जाता है।

Orders of common functions

Further information: 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.

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, where $\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

The statement $f(n)=O(n!)$ is sometimes weakened to $f(n)=O\left(n^{n}\right)$ to derive simpler formulas for asymptotic complexity. For any $k>0$ and $c>0$, $O(n^{c}(\log n)^{k})$ is a subset of $O(n^{c+\varepsilon })$ for any $\varepsilon >0$, so may be considered as a polynomial with some bigger order.

कंप्यूटर विज्ञान में उपयोग

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

अनौपचारिक रूप से, विशेष रूप से कंप्यूटर विज्ञान में, बड़े O नोटेशन का उपयोग अधिकांशतः एसिम्प्टोटिक ऊपरी और निचले सीमा # तंग सीमा का वर्णन करने के लिए कुछ अलग विधि से किया जा सकता है, जहां बड़े थीटा Θ नोटेशन का उपयोग किसी दिए गए संदर्भ में तथ्यात्मक रूप से अधिक उपयुक्त हो सकता है। उदाहरण के लिए, किसी फलन T(n) = 73n³+22n² + 58 पर विचार करते समय, निम्नलिखित में से सभी सामान्यतः स्वीकार्य हैं, किन्तु कड़ी सीमाएं (जैसे नीचे संख्या 2 और 3) सामान्यतः सरल सीमाओं (जैसे नीचे संख्या 1) की तुलना में दृढ़ता से पसंद की जाती हैं।

1. T(n) = O(n¹⁰⁰)
2. T(n) = O(n³)
3. T(n) = Θ(n³)

समतुल्य अंग्रेजी कथन क्रमशः हैं:

1. T(n) बिना किसी लक्षण के n¹⁰⁰ से अधिक तेजी से बढ़ता है
2. T(n) बिना किसी लक्षण के n³ से अधिक तेजी से बढ़ता है
3. T(n) n³ जितनी तेजी से लक्षणहीन रूप से बढ़ता है.

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

अन्य संकेतन

अपनी पुस्तक एल्गोरिदम का परिचय में, थॉमस एच. कॉर्मेन, चार्ल्स ई. लेइसर्सन, रोनाल्ड एल. रिवेस्ट और क्लिफोर्ड स्टीन ने फलन के सेट पर विचार किया है जो संतुष्ट करता है

$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}\}.$$

लेखकों का कहना है कि सेट सदस्यता ऑपरेटर (∈) के अतिरिक्त सेट सदस्यता को दर्शाने के लिए समानता ऑपरेटर (=) का उपयोग नोटेशन का दुरुपयोग है, किन्तु ऐसा करने के लाभ हैं। किसी समीकरण या असमानता के अंदर, एसिम्प्टोटिक नोटेशन का उपयोग सेटO (जी) में अज्ञात फलन के लिए होता है, जो निम्न-क्रम वाले शब्दों को समाप्त करता है, और समीकरणों में अनावश्यक अव्यवस्था को कम करने में मदद करता है, उदाहरण के लिए:

$2n^{2}+3n+1=2n^{2}+O(n).$

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

कंप्यूटर विज्ञान में कभी-कभी उपयोग किया जाने वाला अन्य संकेतन Õ (सॉफ्ट-ओ पढ़ें) है, जो पॉलीलॉगरिदमिक कारकों को छुपाता है। उपयोग में दो परिभाषाएँ हैं: कुछ लेखक f(n)=Õ(g(n)) को आशुलिपि के रूप में उपयोग करते हैं f(n) = O(g(n) log^k n) कुछ k के लिए, जबकि अन्य इसे शॉर्टहैंड के रूप में उपयोग करते हैं f(n) = O(g(n) log^k g(n)). कब g(n) n में बहुपद है, कोई अंतर नहीं है;चूँकि, बाद वाली परिभाषा किसी को यह कहने की अनुमति देती है, उदाहरण के लिए वह $n2^{n}={\tilde {O}}(2^{n})$ जबकि पूर्व परिभाषा इसकी अनुमति देती है $\log ^{k}n={\tilde {O}}(1)$ किसी स्थिरांक k के लिए। कुछ लेखकO लिखते हैं^*बाद वाली परिभाषा के समान उद्देश्य के लिए। अनिवार्य रूप से, यह बड़ा O नोटेशन है, पॉलीलॉगरिदमिक फलन को अनदेखा कर रहा है क्योंकि एसिम्प्टोटिक विश्लेषण | कुछ अन्य सुपर-लघुगणकीय फलन के विकास-दर प्रभाव बड़े आकार के इनपुट मापदंड के लिए विकास-दर विस्फोट का संकेत देते हैं जो खराब रन-टाइम प्रदर्शन की पूर्वानुमान करने के लिए अधिक महत्वपूर्ण है लघुगणक-विकास कारक (ओं) द्वारा योगदान किए गए उत्तम-बिंदु प्रभावों की तुलना में। इस संकेतन का उपयोग अधिकांशतः विकास-दर के अन्दर होने वाली खामियों को दूर करने के लिए किया जाता है, जिन्हें वर्तमान स्थितियों के लिए बहुत कसकर बांधा गया है (लॉग के बाद से) किसी भी स्थिरांक k और किसी के लिए ε > 0).

इसके अतिरिक्त एल-नोटेशन, के रूप में परिभाषित किया गया है

$L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}$

उन फलनों के लिए सुविधाजनक है जो समय जटिलता#बहुपद समय और समय जटिलता#घातीय समय के बीच हैं $\ln n$.

सामान्यीकरण और संबंधित उपयोग

किसी भी मानक वेक्टर स्थान में मान लेने वाले फलनों का सामान्यीकरण सीधा है (मानदंडों द्वारा निरपेक्ष मानों को प्रतिस्थापित करना), जहां एफ और जी को ही स्थान में अपने मान लेने की आवश्यकता नहीं है। किसी भी टोपोलॉजिकल समूह में मान लेने वाले फलनों का सामान्यीकरण भी संभव है

सीमित प्रक्रिया x → x_o मनमाना फ़िल्टर आधार, अर्थात निर्देशित नेट (गणित) एफ और जी को प्रस्तुत करके भी सामान्यीकृत किया जा सकता है। O नोटेशन का उपयोग अधिक सामान्य स्थानों में यौगिक और भिन्नता को परिभाषित करने के लिए किया जा सकता है, और फलनों की (स्पर्शोन्मुख) समतुल्यता को भी परिभाषित करने के लिए किया जा सकता है,

$f\sim g\iff (f-g)\in o(g)$

जो कि तुल्यता संबंध है और संबंध f की तुलना में अधिक प्रतिबंधात्मक धारणा है, ऊपर से Θ(g) है। (यदि एफ और जी सकारात्मक वास्तविक मूल्य वाले फलन हैं तो यह लिम एफ/जी = 1 तक कम हो जाता है।) उदाहरण के लिए, 2x Θ(x) है, किन्तु 2x − xO(x) नहीं है।

इतिहास (बाचमन-लैंडौ, हार्डी, और विनोग्राडोव नोटेशन)

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

प्रतीक $\Omega$ (इस अर्थ मेंO का कोई कारण नहीं है) 1914 में हार्डी और लिटिलवुड द्वारा प्रस्तुत किया गया था। हार्डी और लिटिलवुड ने भी 1916 में प्रतीकों की प्रारंभ की $\Omega _{R}$ (दाएं) और $\Omega _{L}$ ( बाएं ), आधुनिक प्रतीकों के अग्रदूत $\Omega _{+}$ (एक छोटे से O से छोटा नहीं है) और $\Omega _{-}$ (के छोटे से से बड़ा नहीं है). इस प्रकार ओमेगा प्रतीकों (उनके मूल अर्थ के साथ) को कभी-कभी लैंडौ प्रतीकों के रूप में भी जाना जाता है। यह संकेतन $\Omega$ कम से कम 1950 के दशक से संख्या सिद्धांत में इसका सामान्यतः उपयोग किया जाने लगा।

1970 के दशक में बिगओको डोनाल्ड नुथ द्वारा कंप्यूटर विज्ञान में लोकप्रिय बनाया गया, जिन्होंने संबंधित थीटा नोटेशन की प्रारंभ की, और ओमेगा नोटेशन के लिए अलग परिभाषा प्रस्तावित की।

लैंडौ ने कभी भी बड़े थीटा और छोटे ओमेगा प्रतीकों का उपयोग नहीं किया।

हार्डी के प्रतीक थे (आधुनिकO अंकन के संदर्भ में)

$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 शेष पत्रों और पुस्तकों में उन्होंने लगातार लैंडौ प्रतीकोंO औरO का उपयोग किया।

हार्डी के नोटेशन का अब उपयोग नहीं किया जाता है। दूसरी ओर, 1930 के दशक में, रूसी संख्या सिद्धांतकार इवान मतवेयेविच विनोग्रादोव ने अपना अंकन प्रस्तुत किया $\ll$, जिसका उपयोग संख्या सिद्धांत के अतिरिक्त तेजी से किया जा रहा है $O$ अंकन. अपने पास

$f\ll g\iff f\in O(g),$

और अधिकांशतः दोनों नोटेशन का उपयोग ही पेपर में किया जाता है।

बिग-ओ मूल रूप से ऑर्डर ऑफ (ऑर्डनंग, बैचमैन 1894) को दर्शाता है, और इस प्रकार यह लैटिन अक्षर है। न तो बैचमैन और न ही लैंडौ ने कभी इसे ऑमिक्रॉन कहा। इस प्रतीक को बहुत बाद में (1976) नुथ ने बड़े ओमीक्रॉन के रूप में देखा,संभवतः प्रतीक ओमेगा की उनकी परिभाषा के संदर्भ में। अंक 0 का प्रयोग नहीं किया जाना चाहिए.

यह भी देखें

• स्पर्शोन्मुख विस्तार: टेलर के सूत्र को सामान्य बनाने वाले फलनों का सन्निकटन
• एसिम्प्टोटिक रूप से इष्टतम एल्गोरिदम: वाक्यांश जो अधिकांशतः एल्गोरिदम का वर्णन करने के लिए उपयोग किया जाता है जिसमें समस्या के लिए निचली सीमा के स्थिरांक के अन्दर एसिम्प्टोटिक रूप से ऊपरी सीमा होती है
• संभाव्यता संकेतन में बड़ा O: O_p, o_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-ओ नोटेशन – What is it good for
• An example of BigO 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

|}