बिग ओ नोटेशन को समझना और निर्धारित करना

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

बिग ओ क्यों महत्वपूर्ण है?

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

सामान्य बिग ओ नोटेशन (सबसे अच्छे से सबसे खराब तक):

यहाँ सामान्य बिग ओ जटिलताओं की एक सूची दी गई है, जो सबसे अधिक से कम कुशल तक क्रमबद्ध हैं:

O(1) - स्थिर समय: इनपुट आकार की परवाह किए बिना एल्गोरिदम समान समय लेता है। उदाहरण: किसी सरणी में किसी तत्व को उसके इंडेक्स द्वारा एक्सेस करना, सरल अंकगणितीय ऑपरेशन।
O(log n) - लॉगरिदमिक समय: लिया गया समय इनपुट आकार के साथ लॉगरिदमिक रूप से बढ़ता है। यह बहुत कुशल है। उदाहरण: सॉर्टेड ऐरे में बाइनरी सर्च। सर्च स्पेस को बार-बार आधा करने के बारे में सोचें।
O(n) - रैखिक समय: लिया गया समय इनपुट आकार के साथ रैखिक रूप से बढ़ता है। उदाहरण: एक बार ऐरे से गुजरना, अनसॉर्टेड ऐरे में अधिकतम तत्व ढूँढना।
O(n log n) - रैखिक समय: रैखिक और लघुगणक का संयोजन। अक्सर कुशल सॉर्टिंग एल्गोरिदम में पाया जाता है। उदाहरण: मर्ज सॉर्ट, क्विकसॉर्ट (औसतन), हीपसॉर्ट।
O(n²) - क्वाड्रैटिक समय: लिया गया समय इनपुट आकार के वर्ग के अनुपात में बढ़ता है। नेस्टेड लूप के साथ आम। उदाहरण: बबल सॉर्ट, इंसर्शन सॉर्ट, सिलेक्शन सॉर्ट।
O(n³) - क्यूबिक समय: लिया गया समय इनपुट आकार के क्यूब के अनुपात में बढ़ता है। ट्रिपल नेस्टेड लूप एक आम स्रोत हैं।
O(2ⁿ) - एक्सपोनेंशियल टाइम: इनपुट में प्रत्येक जोड़ के साथ लिया गया समय दोगुना हो जाता है। ये एल्गोरिदम बहुत जल्दी बहुत धीमे हो जाते हैं। उदाहरण: पुनरावर्ती फिबोनाची (सरल कार्यान्वयन), किसी सेट के सभी उपसमूहों को ढूँढना।
O(n!) - फैक्टोरियल टाइम: लिया गया समय इनपुट आकार के साथ फैक्टोरियल रूप से बढ़ता है। ये सबसे छोटे इनपुट को छोड़कर किसी भी चीज़ के लिए बेहद अक्षम हैं। उदाहरण: किसी स्ट्रिंग के सभी क्रमपरिवर्तन ढूँढना।

बिग ओ नोटेशन कैसे निर्धारित करें (सामान्य नियम)

यहाँ एक कोड स्निपेट के बिग ओ नोटेशन को निर्धारित करने के लिए चरण-दर-चरण दृष्टिकोण दिया गया है:

इनपुट की पहचान करें: निर्धारित करें कि "इनपुट आकार" (आमतौर पर 'n' द्वारा दर्शाया जाता है) क्या होता है। यह किसी सरणी में तत्वों की संख्या, स्ट्रिंग की लंबाई, डेटा संरचना का आकार आदि हो सकता है।
विश्लेषण लूप:

एकल लूप: एक लूप जो एक बार इनपुट के माध्यम से पुनरावृत्त होता है, आमतौर पर O(n) जटिलता में योगदान देता है।
नेस्टेड लूप: नेस्टेड लूप आम तौर पर जटिलताओं को गुणा करते हैं। एक ही इनपुट पर पुनरावृत्त होने वाले दो नेस्टेड लूप O(n²) हैं। तीन नेस्टेड लूप O(n³) हैं, और इसी तरह।
लॉगरिदमिक व्यवहार वाला लूप: यदि कोई लूप इनपुट आकार को लगातार एक स्थिर कारक (जैसे, बाइनरी सर्च) से विभाजित करता है, तो यह संभवतः O(log n) जटिलता में योगदान देता है।

फ़ंक्शन कॉल का विश्लेषण करें:

पुनरावर्ती कॉल: पुनरावर्ती फ़ंक्शन की जटिलता पुनरावर्ती कॉल की संख्या और प्रत्येक कॉल में किए गए कार्य पर निर्भर करती है। मास्टर प्रमेय जैसी तकनीकें पुनरावर्ती कार्यों का विश्लेषण करने में मदद कर सकती हैं। सरल पुनरावर्ती कार्य घातांकीय (O(2ⁿ)) या फैक्टोरियल (O(n!)) भी हो सकते हैं।
अन्य फ़ंक्शन कॉल: यदि आपका कोड अन्य फ़ंक्शन कॉल करता है, तो आपको उनकी बिग O जटिलताओं पर विचार करने की आवश्यकता है। यदि आप O(n) लूप के अंदर O(n²) फ़ंक्शन को कॉल करते हैं, तो समग्र जटिलता O(n³) हो जाती है।

स्थिरांक हटाएँ: स्थिरांक कारकों को अनदेखा करें। O(2n) और O(n) दोनों को O(n) माना जाता है। बिग O विकास दर के बारे में है, सटीक समय के बारे में नहीं।
निम्न-क्रम शब्द हटाएँ: केवल प्रमुख शब्द रखें। उदाहरण के लिए, O(n² + n) को O(n²) में सरलीकृत किया जाता है, क्योंकि n² n की तुलना में बहुत तेज़ी से बढ़ता है।
सर्वश्रेष्ठ, औसत और सबसे खराब स्थिति:

सबसे खराब स्थिति जटिलता: सबसे आम और आम तौर पर सबसे महत्वपूर्ण स्थिति। यह एल्गोरिदम के संसाधन उपयोग पर एक ऊपरी सीमा प्रदान करता है। जब हम बस "बिग ओ" कहते हैं तो हमारा मतलब आमतौर पर यही होता है।
औसत-स्थिति जटिलता: कई बार चलाने पर अपेक्षित प्रदर्शन का वर्णन करता है। अक्सर सटीक रूप से निर्धारित करना कठिन होता है।
सर्वश्रेष्ठ-स्थिति जटिलता: सबसे कुशल परिदृश्य का वर्णन करता है। व्यवहार में कम उपयोगी है, क्योंकि यह सामान्य प्रदर्शन का प्रतिनिधित्व नहीं करता है।

उदाहरण

आइए कुछ कोड स्निपेट का विश्लेषण करें:

उदाहरण 1: ऐरे एलिमेंट तक पहुँचना

function getElement(arr, index) {
return arr[index];
}

इनपुट: ऐरे arr और index। सरणी का आकार (arr.length) इनपुट आकार 'n' है।
विश्लेषण: सरणी के आकार की परवाह किए बिना, इंडेक्स द्वारा सरणी तत्व तक पहुँचने में निरंतर समय लगता है।
बिग ओ: O(1)

उदाहरण 2: रैखिक खोज

function linearSearch(arr, target) {
for (let i = 0; i < arr.length; i++) {
if (arr[i] === target) {
return i;
}
}
return -1;
}

इनपुट: सरणी arr और target। सरणी का आकार (arr.length) 'n' है।
विश्लेषण: लूप अधिकतम 'n' बार (सरणी की लंबाई) पर पुनरावृत्त होता है।
बिग ओ: O(n)

उदाहरण 3: नेस्टेड लूप्स (बबल सॉर्ट)

function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// तत्वों को स्वैप करें
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}

इनपुट: सरणी arr. सरणी (arr.length) का आकार 'n' है.
विश्लेषण: हमारे पास दो नेस्टेड लूप हैं. बाहरी लूप 'n' बार चलता है। आंतरिक लूप लगभग 'n' बार चलता है (यह प्रत्येक बाहरी लूप पुनरावृत्ति के साथ थोड़ा कम हो जाता है, लेकिन यह एक निम्न-क्रम शब्द है जिसे हम अनदेखा कर सकते हैं)। इसलिए, प्रमुख ऑपरेशन (तुलना) लगभग n * n = n² बार निष्पादित किया जाता है।
बिग O: O(n²)

उदाहरण 4: बाइनरी सर्च

function binarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;

while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] === target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}

इनपुट: सॉर्टेड ऐरे arr और target. ऐरे का आकार (arr.length) 'n' है.
विश्लेषण: while लूप के प्रत्येक पुनरावृत्ति में, हम प्रभावी रूप से खोज स्थान को आधा कर देते हैं. यह आधा करना तब तक जारी रहता है जब तक कि लक्ष्य नहीं मिल जाता या खोज स्थान खाली नहीं हो जाता. हम जितनी बार 'n' को आधा कर सकते हैं वह log₂(n) (लॉगरिदम बेस 2) है.
बिग O: O(log n)

उदाहरण 5: रिकर्सिव फाइबोनैचि (नाइव)

function fibonacci(n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}

इनपुट: पूर्णांक n.
विश्लेषण: fibonacci(n) (जहाँ n > 1) के प्रत्येक कॉल के लिए, हम दो और पुनरावर्ती कॉल करते हैं. इससे कॉल का एक शाखा वृक्ष बनता है. 'n' में प्रत्येक वृद्धि के साथ कॉल की संख्या लगभग दोगुनी हो जाती है.
बड़ा O: O(2ⁿ) (यह एक सरलीकरण है. वास्तविक जटिलता O(1.618ⁿ) के करीब है, लेकिन प्रमुख शब्द घातांकीय है.)

उदाहरण 6: लूप के अंदर फ़ंक्शन कॉल


function doSomething(arr) {
for (let i = 0; i < arr.length; i++) {
anotherFunction(arr[i]);
}
}

function anotherFunction(value){
for (let j=0; j<value; j++){
console.log(j);
}
}

इनपुट: arr, जहाँ n = arr.length
विश्लेषण:
doSomething n बार पुनरावृत्त होता है।
anotherFunction, लूप के अंदर, की जटिलता O(m) है जहाँ m इनपुट value का आकार है। सबसे खराब स्थिति में, value n के समानुपातिक हो सकता है। इसलिए anotherFunction O(n) है
चूँकि anotherFunction को doSomething के लूप के अंदर बुलाया जाता है, इसलिए जटिलताएँ कई गुना बढ़ जाती हैं।
बिग O: O(n * n) = O(n²)

निष्कर्ष