algorithm
बिग-ओ नोटेशन
खोज…
टिप्पणियों
परिभाषा
बिग-ओ नोटेशन उसके दिल में एक गणितीय अंकन है, जिसका उपयोग कार्यों के अभिसरण की दर की तुलना करने के लिए किया जाता है। प्राकृतिक संख्याओं पर परिभाषित n -> f(n) और n -> g(n) कार्य होने दें। तब हम कहते हैं कि f = O(g) यदि और केवल अगर f(n)/g(n) तब बंधे हुए हैं जब n अनंतता के निकट आता है। दूसरे शब्दों में, f = O(g) यदि और केवल अगर कोई निरंतर A मौजूद है, तो ऐसे सभी n, f(n)/g(n) <= A ।
वास्तव में बिग-ओ नोटेशन का दायरा गणित में थोड़ा व्यापक है, लेकिन सादगी के लिए मैंने इसे एल्गोरिथ्म जटिलता विश्लेषण में उपयोग किया जाता है: नॅकल्स पर परिभाषित कार्य, जिसमें गैर-शून्य मान हैं, और एन के बढ़ने का मामला अनन्त तक।
इसका क्या मतलब है ?
चलो f(n) = 100n^2 + 10n + 1 और g(n) = n^2 का मामला लेते हैं। यह बिल्कुल स्पष्ट है कि इन दोनों कार्यों को अनंतता के रूप में जाना जाता है क्योंकि एन अनंत तक जाता है। लेकिन कभी-कभी सीमा जानना पर्याप्त नहीं होता है, और हम उस गति को भी जानना चाहते हैं जिस पर फ़ंक्शन उनकी सीमा तक पहुंचते हैं। बिग-ओ जैसी धारणाएँ अभिसरण की गति द्वारा कार्यों की तुलना और वर्गीकरण में मदद करती हैं।
आइए जानें कि परिभाषा को लागू करके यदि f = O(g) है। हमारे पास f(n)/g(n) = 100 + 10/n + 1/n^2 । के बाद से 10/n 10 जब n 1 है और कम हो रही है, और के बाद से 1/n^2 1 है जब n 1 है और यह भी कम हो रही है, हम च f(n)/g(n) <= 100 + 10 + 1 = 111 । परिभाषा संतुष्ट है क्योंकि हमने f(n)/g(n) (111) और इसलिए f = O(g) एक सीमा पाई है (हम कहते हैं कि f, n^2 का Big-O है)।
इसका मतलब यह है कि एफ लगभग उसी गति से अनंत तक जाता है जैसे जी। अब यह कहना एक विचित्र बात लग सकती है, क्योंकि हमने जो पाया है वह यह है कि f, जी की तुलना में 111 गुना ज्यादा बड़ा है, या दूसरे शब्दों में जब g 1 से बढ़ता है, तो f 111 से बढ़ता है। ऐसा लग सकता है कि बढ़ता जा रहा है 111 गुना तेज "लगभग समान गति" नहीं है। और वास्तव में बिग-ओ नोटेशन फ़ंक्शन कनवर्जेन्स गति को वर्गीकृत करने का एक बहुत सटीक तरीका नहीं है, यही वजह है कि गणित में हम गति के सटीक अनुमान का उपयोग करते समय समतुल्य संबंध का उपयोग करते हैं। लेकिन बड़ी गति कक्षाओं में एल्गोरिदम को अलग करने के प्रयोजनों के लिए, बिग-ओ पर्याप्त है। हम अलग कार्यों कि तेजी से एक दूसरे को की तुलना में समय की एक निश्चित संख्या के बढ़ने, लेकिन केवल कार्यों कि असीम बढ़ने तेजी से एक दूसरे को की तुलना में की जरूरत नहीं है। उदाहरण के लिए यदि हम h(n) = n^2*log(n) लेते हैं, तो हम देखते हैं कि h(n)/g(n) = log(n) जो n के साथ अनंत तक जाता है, तो O नहीं है (n ^) 2), क्योंकि ज असीम तेजी से n ^ 2 से बढ़ता है।
अब मुझे एक साइड नोट करने की आवश्यकता है: आपने देखा होगा कि यदि f = O(g) और g = O(h) , तो f = O(h) । उदाहरण के लिए, हमारे मामले में, हमारे पास f = O(n^3) , और f = O(n^4) ... एल्गोरिथ्म जटिलता विश्लेषण में, हम अक्सर f = O(g) का मतलब है कि f = O(g) और g = O(f) , जिसे "g, f के लिए सबसे छोटा Big-O है" के रूप में समझा जा सकता है। गणित में हम कहते हैं कि ऐसे कार्य एक-दूसरे के बिग-थेटा हैं।
इसका उपयोग कैसे किया जा सकता है ?
एल्गोरिदम के प्रदर्शन की तुलना करते समय, हम उन कार्यों की संख्या में रुचि रखते हैं जो एक एल्गोरिथ्म निष्पादित करता है। इसे समय जटिलता कहा जाता है । इस मॉडल में, हम मानते हैं कि प्रत्येक मूल ऑपरेशन (जोड़, गुणा, तुलना, असाइनमेंट, आदि) को एक निश्चित समय लगता है, और हम इस तरह के ऑपरेशन की संख्या की गणना करते हैं। हम आम तौर पर इस संख्या को इनपुट के आकार के एक फ़ंक्शन के रूप में व्यक्त कर सकते हैं, जिसे हम n कहते हैं। और दुख की बात है कि यह संख्या आमतौर पर n के साथ अनंत तक बढ़ती है (यदि ऐसा नहीं है, तो हम कहते हैं कि एल्गोरिथ्म ओ (1) है)। हम बिग-ओ द्वारा परिभाषित बड़ी गति कक्षाओं में अपने एल्गोरिदम को अलग करते हैं: जब हम "ओ (एन ^ 2) एल्गोरिथ्म" के बारे में बोलते हैं, तो हमारा मतलब है कि यह कितने ऑपरेशन करता है, एन के एक फ़ंक्शन के रूप में व्यक्त किया जाता है, एक हे ( n ^ 2)। यह कहता है कि हमारा एल्गोरिथ्म लगभग एक एल्गोरिथ्म जितना तेज़ है, जो इसके इनपुट के आकार के वर्ग के बराबर कई ऑपरेशन करेगा, या तेज़ी से । "या तेज" भाग वहाँ है क्योंकि मैंने बिग-थीटा के बजाय बिग-ओ का उपयोग किया था, लेकिन आमतौर पर लोग बिग-ओ को बिग-थीटा कहेंगे।
संचालन की गणना करते समय, हम आमतौर पर सबसे खराब स्थिति पर विचार करते हैं: उदाहरण के लिए यदि हमारे पास एक लूप है जो अधिकांश n समय पर चल सकता है और जिसमें 5 ऑपरेशन हैं, तो हमारे द्वारा गिने जाने वाले ऑपरेशन की संख्या 5n है। औसत मामले की जटिलता पर विचार करना भी संभव है।
त्वरित नोट: एक तेज़ एल्गोरिदम वह है जो कुछ संचालन करता है, इसलिए यदि संचालन की संख्या तेजी से अनंत तक बढ़ती है, तो एल्गोरिथ्म धीमा है : O (n) O (n ^ 2) से बेहतर है।
हम कभी-कभी अपने एल्गोरिथ्म के अंतरिक्ष जटिलता में भी रुचि रखते हैं। इसके लिए हम एल्गोरिथ्म में व्याप्त मेमोरी की संख्या को इनपुट के आकार के एक फ़ंक्शन के रूप में मानते हैं, और उसी तरह बिग-ओ का उपयोग करते हैं।
एक साधारण लूप
निम्नलिखित फ़ंक्शन एक सरणी में अधिकतम तत्व पाता है:
int find_max(const int *array, size_t len) {
int max = INT_MIN;
for (size_t i = 0; i < len; i++) {
if (max < array[i]) {
max = array[i];
}
}
return max;
}
इनपुट आकार सरणी का आकार है, जिसे मैंने कोड में len कहा है।
चलो ऑपरेशन गिनते हैं।
int max = INT_MIN;
size_t i = 0;
ये दो कार्य केवल एक बार किए जाते हैं, इसलिए यह 2 कार्य हैं। लूप किए गए कार्य हैं:
if (max < array[i])
i++;
max = array[i]
चूंकि लूप में 3 ऑपरेशन हैं, और लूप को एन बार किया जाता है, हम 3n + 2 प्राप्त करने के लिए अपने पहले से मौजूद 2 ऑपरेशनों में 3n जोड़ते हैं। तो हमारा फ़ंक्शन अधिकतम खोजने के लिए 3n + 2 संचालन लेता है (इसकी जटिलता 3n + 2 )। यह एक बहुपद है जहां सबसे तेजी से बढ़ता शब्द n का एक कारक है, इसलिए यह O (n) है।
आपने शायद देखा है कि "ऑपरेशन" बहुत अच्छी तरह से परिभाषित नहीं है। उदाहरण के लिए मैंने कहा कि if (max < array[i]) एक ऑपरेशन था, लेकिन आर्किटेक्चर के आधार पर यह कथन तीन निर्देशों का संकलन कर सकता है: एक मेमोरी रीड, एक तुलना और एक शाखा। मैंने सभी ऑपरेशनों को भी समान माना है, उदाहरण के लिए भले ही मेमोरी ऑपरेशन दूसरों की तुलना में धीमा होगा, और कैशे इफेक्ट्स के कारण उनका प्रदर्शन बेतहाशा भिन्न होगा। मैंने रिटर्न स्टेटमेंट को भी पूरी तरह से नजरअंदाज कर दिया है, तथ्य यह है कि फ़ंक्शन के लिए एक फ्रेम बनाया जाएगा, आदि। अंत में यह जटिलता विश्लेषण के लिए कोई फर्क नहीं पड़ता, क्योंकि मैं जिस किसी भी तरह से ऑपरेशन गिनता हूं, वह केवल गुणांक को बदल देगा। n कारक और स्थिर है, इसलिए परिणाम अभी भी O (n) होगा। जटिलता से पता चलता है कि एल्गोरिथ्म इनपुट के आकार के साथ कैसे मापता है, लेकिन यह प्रदर्शन का एकमात्र पहलू नहीं है!
एक नेस्टेड लूप
निम्न फ़ंक्शन यह जाँचता है कि यदि किसी सरणी में प्रत्येक तत्व को लेकर कोई डुप्लिकेट है, तो पूरे सरणी पर यह देखने के लिए कि क्या तत्व है
_Bool contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len; j++) {
if (i != j && array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
आंतरिक लूप प्रत्येक पुनरावृत्ति पर कई ऑपरेशन करता है जो n साथ निरंतर होता है। बाहरी लूप भी कुछ निरंतर संचालन करता है, और आंतरिक लूप n बार चलाता है। बाहरी लूप स्वयं n बार चलाया जाता है। तो इनर लूप के अंदर का संचालन n^2 बार चलाया जाता है, बाहरी लूप में संचालन n बार चलाया जाता है, और i को असाइनमेंट एक बार किया जाता है। इस प्रकार, जटिलता an^2 + bn + c जैसी कुछ होगी, और चूंकि उच्चतम शब्द n^2 , O अंकन O(n^2) ।
जैसा कि आपने देखा होगा, हम कई बार एक ही तुलना करने से बचकर एल्गोरिथ्म में सुधार कर सकते हैं। हम आंतरिक लूप में i + 1 से शुरू कर सकते हैं, क्योंकि इससे पहले के सभी तत्वों को पहले से ही सभी सरणी तत्वों के खिलाफ जांचा जाएगा, जिसमें इंडेक्स i + 1 । यह हमें i == j चेक को छोड़ने की अनुमति देता है।
_Bool faster_contains_duplicates(const int *array, size_t len) {
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (array[i] == array[j]) {
return 1;
}
}
}
return 0;
}
जाहिर है, यह दूसरा संस्करण कम संचालन करता है और इसलिए अधिक कुशल है। बिग-ओ नोटेशन में कैसे अनुवाद होता है? खैर, अब आंतरिक लूप बॉडी को 1 + 2 + ... + n - 1 = n(n-1)/2 बार चलाया जाता है। यह अभी भी दूसरी डिग्री का एक बहुपद है, और इसलिए अभी भी केवल O(n^2) । हमने स्पष्ट रूप से जटिलता को कम कर दिया है, क्योंकि हम लगभग 2 आपरेशनों की संख्या से विभाजित हैं जो हम कर रहे हैं, लेकिन हम अभी भी उसी जटिलता वर्ग में हैं जैसे कि बिग-ओ द्वारा परिभाषित किया गया है। एक निम्न वर्ग के लिए जटिलता को कम करने के लिए हमें कुछ के द्वारा संचालन की संख्या को विभाजित करने की आवश्यकता होगी जो n साथ अनन्तता को जाता है ।
एक O (लॉग एन) उदाहरण
परिचय
निम्नलिखित समस्या पर विचार करें:
L एक क्रमबद्ध युक्त सूची है n पर हस्ताक्षर किए पूर्णांक ( n बड़ा पर्याप्त जा रहा है), उदाहरण के लिए [-5, -2, -1, 0, 1, 2, 4] (यहाँ, n 7 के एक मूल्य है)। यदि L को पूर्णांक 0 समाहित करने के लिए जाना जाता है, तो आप 0 का सूचकांक कैसे खोज सकते हैं?
Naïve दृष्टिकोण
पहली बात जो मन में आती है वह है कि जब तक 0 नहीं मिल जाता तब तक हर इंडेक्स को पढ़ें। सबसे खराब स्थिति में, संचालन की संख्या n , इसलिए जटिलता O (n) है।
यह n छोटे मूल्यों के लिए ठीक काम करता है, लेकिन क्या अधिक कुशल तरीका है?
विरोधाभास
निम्नलिखित एल्गोरिथ्म (पायथन 3) पर विचार करें:
a = 0
b = n-1
while True:
h = (a+b)//2 ## // is the integer division, so h is an integer
if L[h] == 0:
return h
elif L[h] > 0:
b = h
elif L[h] < 0:
a = h
a और b वे इंडेक्स हैं जिनके बीच 0 पाया जाना है। हर बार जब हम लूप में प्रवेश करते हैं, तो हम a और b बीच a सूचकांक का उपयोग करते हैं और इसे खोजे जाने वाले क्षेत्र को संकीर्ण करने के लिए उपयोग करते हैं।
सबसे खराब स्थिति में, हमें a और b बराबर होने तक इंतजार करना होगा। लेकिन कितने ऑपरेशन होते हैं? एन नहीं, क्योंकि हर बार जब हम लूप में प्रवेश करते हैं, तो हम a और b बीच की दूरी को लगभग दो से विभाजित करते हैं। बल्कि, जटिलता हे (लॉग एन) है।
व्याख्या
नोट: जब हम "लॉग" लिखते हैं, तो हमारा मतलब है बाइनरी लॉगरिदम, या लॉग बेस 2 (जिसे हम "log_2" लिखेंगे)। जैसा कि O (log_2 n) = O (log n) (आप गणित कर सकते हैं) हम "log_2" के बजाय "log" का उपयोग करेंगे।
आइए x को संचालन की संख्या कहते हैं: हम जानते हैं कि 1 = n / (2 ^ x)।
तो 2 ^ x = n, फिर x = log n
निष्कर्ष
जब क्रमिक विभाजनों का सामना करना पड़ता है (यह दो या किसी भी संख्या से हो), याद रखें कि जटिलता लॉगरिदमिक है।
O (लॉग एन) एल्गोरिदम के प्रकार
मान लीजिए कि हमें आकार n की समस्या है। अब हमारे एल्गोरिथ्म के प्रत्येक चरण के लिए (जिसे हमें लिखने की आवश्यकता है), हमारी मूल समस्या इसके पिछले आकार (n / 2) से आधी हो जाती है।
इसलिए प्रत्येक कदम पर, हमारी समस्या आधी हो जाती है।
| चरण | मुसीबत |
|---|---|
| 1 | n / 2 |
| 2 | n / 4 |
| 3 | n / 8 |
| 4 | n / 16 |
जब समस्या की जगह कम हो जाती है (अर्थात पूरी तरह से हल हो जाती है), तो चेक की स्थिति से बाहर निकलने के बाद इसे और कम नहीं किया जा सकता है (n 1 के बराबर हो जाता है)।
मान लीजिए कि आप कदम या संचालन की संख्या पर हैं:
समस्या-आकार = १
लेकिन हम kth कदम पर जानते हैं, हमारी समस्या का आकार निम्न होना चाहिए:
समस्या-आकार = n / 2 k
1 और 2 से:
n / 2 k = 1 या
n = 2 के
दोनों तरफ से लॉग इन करें
log e n = k log e 2
या
k = log e n / लॉग ई 2
सूत्र लॉग x m / log x n = log n m का उपयोग करें
k = लॉग 2 एन
या बस k = log n
अब हम जानते हैं कि हमारा एल्गोरिथ्म अधिकतम लॉग एन तक चला सकता है, इसलिए समय की जटिलता आती है
O (लॉग एन)
पाठ के ऊपर समर्थन के लिए कोड में एक बहुत ही सरल उदाहरण है:
for(int i=1; i<=n; i=i*2)
{
// perform some operation
}
तो अब अगर कोई आपसे पूछता है कि n 256 है तो लूप (या किसी अन्य एल्गोरिथ्म जो इसे समस्या के आकार को आधे में काट देता है) के कितने चरण होंगे, तो आप बहुत आसानी से गणना कर सकते हैं।
k = लॉग 2 256
कश्मीर = 2 2 8 (=> एक एक = 1 लॉग इन करें) लॉग इन करें
के = 8
इसी तरह के मामले के लिए एक और बहुत अच्छा उदाहरण बाइनरी सर्च एल्गोरिथम है ।
int bSearch(int arr[],int size,int item){
int low=0;
int high=size-1;
while(low<=high){
mid=low+(high-low)/2;
if(arr[mid]==item)
return mid;
else if(arr[mid]<item)
low=mid+1;
else high=mid-1;
}
return –1;// Unsuccessful result
}