Table of Contents
- Algorithm Analysis in Hindi – एल्गोरिदम एनालिसिस क्या है?
- A Priori and A Posteriori Analysis in Hindi – अप्रायोरी और अपोस्टीरियोरी एनालिसिस
- Time Complexity in Hindi – टाइम कॉम्प्लेक्सिटी
- Space Complexity in Hindi – स्पेस कॉम्प्लेक्सिटी
- Best, Average and Worst Case Analysis in Hindi – बेस्ट, एवरेज और वर्स्ट केस एनालिसिस
- Asymptotic Notations in Hindi – एसिम्प्टोटिक नोटेशन
- Order of Growth in Hindi – ग्रोथ का क्रम
- FAQs
Algorithm Analysis in Hindi – एल्गोरिदम एनालिसिस क्या है?
Endless Horse – Find End? Play Game- Algorithm analysis किसी algorithm की efficiency जाँचने की process है, जिसमें यह पता किया जाता है कि algorithm को चलने के लिए कितना time और कितनी memory चाहिए।
- इसमें algorithm की तुलना input size n के हिसाब से की जाती है, क्योंकि input बड़ा होने पर time और memory दोनों बढ़ते हैं।
- एक ही problem के कई algorithms हो सकते हैं, और analysis की मदद से उनमें से सबसे अच्छा algorithm चुना जाता है।
- Analysis में मुख्य रूप से दो चीज़ें मापी जाती हैं, Time Complexity और Space Complexity।
- Analysis किसी खास computer, programming language या compiler पर निर्भर नहीं होना चाहिए, इसलिए time को seconds में नहीं, बल्कि steps की गिनती में मापा जाता है।
- Analysis का नतीजा आमतौर पर Big O जैसे asymptotic notations में लिखा जाता है।
Parts of Algorithm Analysis
ये Algorithm Analysis के ही अलग-अलग Parts हैं। ये Parts analysis के हर एक सवाल का जवाब देते हैं, यानी analysis किस तरीके से किया जाए, उसमें क्या मापा जाए, किस input पर मापा जाए, नतीजा कैसे लिखा जाए और algorithms की तुलना कैसे हो।
- A Priori और A Posteriori Analysis: ये analysis करने के दो तरीके हैं, इसलिए इन्हें Analysis के types कहा जा सकता है।
- Time और Space Complexity: ये analysis में मापी जाने वाली दो चीज़ें हैं, इसलिए इन्हें Complexity के types कहा जा सकता है।
- Best, Average और Worst Case: ये एक ही algorithm को अलग-अलग inputs पर परखने के तीन तरीके हैं, और हर case में Time और Space दोनों मापे जा सकते हैं।
- Asymptotic Notations: ये Time और Space के नतीजे को छोटे और तुलना के लायक रूप में लिखने के संकेत हैं, जैसे T(n) = 3n + 4 को O(n) लिखना।
- Order of Growth: यह notations में लिखे नतीजों को छोटे से बड़े क्रम में रखता है, जिससे पता चलता है कि कौन-सा algorithm बड़े input पर बेहतर रहेगा।
A Priori and A Posteriori Analysis in Hindi – अप्रायोरी और अपोस्टीरियोरी एनालिसिस
यह Algorithm Analysis का पहला हिस्सा है, जिसमें तय किया जाता है कि analysis किस तरीके से होगा। Algorithm का analysis दो तरीकों से किया जा सकता है, इसलिए इन्हें Analysis के types कहा जा सकता है। इनमें से पहला तरीका program बनाने से पहले इस्तेमाल होता है और दूसरा program चलाने के बाद।
| आधार | A Priori Analysis | A Posteriori Analysis |
|---|---|---|
| कब किया जाता है | यह algorithm को program के रूप में चलाने से पहले, सिर्फ़ theory के आधार पर किया जाता है। | यह algorithm को program बनाकर किसी computer पर चलाने के बाद किया जाता है। |
| निर्भरता | यह hardware, programming language और compiler पर निर्भर नहीं होता। | यह उस computer, language और compiler पर निर्भर होता है जिस पर program चलाया गया। |
| Result | इसका result input size n के function के रूप में मिलता है, जैसे T(n) = 3n + 4। | इसका result असली समय और memory के रूप में मिलता है, जैसे seconds और bytes। |
| उपयोग | Algorithms की आपस में तुलना करने के लिए यही तरीका इस्तेमाल होता है। | किसी तैयार program की असली performance जाँचने के लिए यह तरीका इस्तेमाल होता है। |
Time Complexity in Hindi – टाइम कॉम्प्लेक्सिटी
Analysis में सबसे पहले यह मापा जाता है कि algorithm कितना time लेता है। Time Complexity और Space Complexity मिलकर Algorithm Analysis में मापी जाने वाली दोनों चीज़ें हैं।
- Time complexity किसी algorithm को पूरा चलने में लगने वाले time की मात्रा है, जिसे input size n के function T(n) के रूप में लिखा जाता है।
- इसे seconds में नहीं, बल्कि basic operations या steps की गिनती में मापा जाता है, ताकि result machine पर निर्भर न रहे।
- Steps गिनने के लिए Frequency Count Method इस्तेमाल होती है, जिसमें यह गिना जाता है कि हर statement कितनी बार चलता है।
1. Frequency Count Method
मान लीजिए हमें n elements वाले array a के सभी elements का जोड़ निकालना है। नीचे के code में हर statement के सामने उसके चलने की संख्या लिखी गई है।
int sum(int a[], int n) {
int s = 0; // 1 बार
int i;
for (i = 0; i < n; i++) { // i = 0: 1 बार, i < n: n + 1 बार, i++: n बार
s = s + a[i]; // n बार
}
return s; // 1 बार
}
सभी की गिनती जोड़ने पर T(n) = 1 + 1 + (n + 1) + n + n + 1 = 3n + 4 मिलता है। इसमें constant और छोटे terms हटाने पर Time Complexity O(n) बनती है।
2. Analysis of Loops
अलग-अलग तरह के loops की Time Complexity नीचे की table में दी गई है।
| Loop | कितनी बार चलता है | Time Complexity |
|---|---|---|
for (i = 1; i <= n; i++) |
Loop की body n बार चलती है। | इसकी Time Complexity O(n) होती है। |
for (i = 1; i <= n; i++)for (j = 1; j <= n; j++) |
बाहर के loop के हर चक्कर में अंदर का loop n बार चलता है, यानी कुल n × n बार। | इसकी Time Complexity O(n2) होती है। |
for (i = 1; i < n; i = i * 2) |
i की value हर बार दुगुनी होती है (1, 2, 4, 8 ...), इसलिए loop लगभग log2 n बार चलता है। | इसकी Time Complexity O(log n) होती है। |
for (i = 1; i <= n; i++)for (j = 1; j <= i; j++) |
अंदर का loop पहली बार 1, दूसरी बार 2 और आखिरी बार n बार चलता है, इसलिए कुल 1 + 2 + ... + n = n(n + 1)/2 बार चलता है। | इसकी Time Complexity O(n2) होती है। |
Space Complexity in Hindi – स्पेस कॉम्प्लेक्सिटी
Time के बाद Algorithm Analysis में दूसरी चीज़ जो मापी जाती है, वह algorithm की memory है, जिसे Space Complexity कहते हैं।
- Space complexity किसी algorithm को चलाने के लिए लगने वाली कुल memory की मात्रा है, जिसे input size n के function के रूप में लिखा जाता है।
- इसमें दो हिस्से होते हैं, Fixed Part और Variable Part।
- Fixed Part में program का code, constants और सामान्य variables की जगह आती है, जो input size पर निर्भर नहीं करती।
- Variable Part में वह जगह आती है जो input size के हिसाब से बदलती है, जैसे arrays, dynamic memory और recursion का call stack।
- Space complexity में input की अपनी जगह भी गिनी जाती है, जबकि Auxiliary Space में सिर्फ़ वह extra जगह गिनी जाती है जो algorithm अपने काम के लिए इस्तेमाल करता है।
S(P) = C + Sp(I)
C = Fixed Part (input size पर निर्भर नहीं)
Sp(I) = Variable Part (input size पर निर्भर)
- ऊपर के sum() function में सिर्फ़ s, i और n जैसे कुछ variables चाहिए, इसलिए इसकी Auxiliary Space O(1) है।
- किसी array की copy बनाने वाले algorithm में n size का नया array बनता है, इसलिए इसकी Auxiliary Space O(n) है।
- Recursive factorial में n stack frames एक साथ memory में रहते हैं, इसलिए इसकी Space Complexity O(n) है।
Best, Average and Worst Case Analysis in Hindi – बेस्ट, एवरेज और वर्स्ट केस एनालिसिस
Time और Space निकालते समय यह भी तय करना पड़ता है कि input कैसा है। एक ही algorithm को अलग-अलग inputs पर अलग-अलग time लग सकता है। इसलिए analysis तीन cases में किया जाता है। नीचे के चित्र में Linear Search का उदाहरण दिखाया गया है, जिसमें key को array में पहली position से एक-एक करके ढूँढा जाता है।
| Case | मतलब | Linear Search में |
|---|---|---|
| Best Case | यह वह स्थिति है जिसमें algorithm सबसे कम time लेता है। | Key पहली position पर मिल जाए, तो सिर्फ़ 1 comparison लगता है, यानी Time Complexity O(1) होती है। |
| Average Case | यह सभी संभावित inputs पर औसतन लगने वाला time है। | Key किसी भी position पर बराबर संभावना से हो, तो औसतन लगभग (n + 1)/2 comparisons लगते हैं, यानी Time Complexity O(n) होती है। |
| Worst Case | यह वह स्थिति है जिसमें algorithm सबसे ज़्यादा time लेता है। | Key आखिरी position पर हो या array में हो ही नहीं, तो n comparisons लगते हैं, यानी Time Complexity O(n) होती है। |
Worst case यह बताता है कि algorithm को इससे ज़्यादा time कभी नहीं लगेगा, इसलिए analysis में आमतौर पर worst case का ही इस्तेमाल किया जाता है।
Asymptotic Notations in Hindi – एसिम्प्टोटिक नोटेशन
Time और Space का नतीजा T(n) = 3n + 4 जैसे function के रूप में मिलता है। इस नतीजे को छोटा और तुलना के लायक रूप में लिखने के लिए asymptotic notations का इस्तेमाल होता है।
- Asymptotic notations वे संकेत हैं जिनसे input size n बहुत बड़ा होने पर algorithm के time या space के growth को लिखा जाता है।
- इनमें constants और छोटे terms को नज़रअंदाज़ किया जाता है, क्योंकि n बड़ा होने पर सबसे बड़ा term ही growth तय करता है।
- तीन मुख्य notations हैं, Big O, Omega और Theta।
1. Big O Notation (O) – Upper Bound
Big O किसी function के growth की ऊपरी सीमा बताता है। अगर ऐसे positive constants c और n0 मौजूद हों कि n ≥ n0 के सभी मानों पर f(n) ≤ c × g(n) हो, तो f(n) = O(g(n)) लिखा जाता है।
f(n) = O(g(n)) अगर f(n) ≤ c × g(n), सभी n ≥ n0 के लिए
मान लीजिए f(n) = 3n + 2 है। n ≥ 2 के लिए 3n + 2 ≤ 4n होता है, इसलिए c = 4 और n0 = 2 लेने पर f(n) = O(n) सिद्ध हो जाता है।
2. Omega Notation (Ω) – Lower Bound
Omega किसी function के growth की निचली सीमा बताता है। अगर ऐसे positive constants c और n0 मौजूद हों कि n ≥ n0 के सभी मानों पर f(n) ≥ c × g(n) हो, तो f(n) = Ω(g(n)) लिखा जाता है।
f(n) = Ω(g(n)) अगर f(n) ≥ c × g(n), सभी n ≥ n0 के लिए
मान लीजिए f(n) = 3n + 2 है। n ≥ 1 के लिए 3n + 2 ≥ 3n होता है, इसलिए c = 3 और n0 = 1 लेने पर f(n) = Ω(n) सिद्ध हो जाता है।
3. Theta Notation (Θ) – Tight Bound
Theta किसी function के growth को ऊपर और नीचे, दोनों तरफ़ से एक ही g(n) के बीच बाँध देता है। अगर ऐसे positive constants c1, c2 और n0 मौजूद हों कि n ≥ n0 के सभी मानों पर c1 × g(n) ≤ f(n) ≤ c2 × g(n) हो, तो f(n) = Θ(g(n)) लिखा जाता है।
f(n) = Θ(g(n)) अगर c1 × g(n) ≤ f(n) ≤ c2 × g(n), सभी n ≥ n0 के लिए
मान लीजिए f(n) = 3n + 2 है। n ≥ 2 के लिए 3n ≤ 3n + 2 ≤ 4n होता है, इसलिए c1 = 3, c2 = 4 और n0 = 2 लेने पर f(n) = Θ(n) सिद्ध हो जाता है।
| Notation | Bound | मतलब |
|---|---|---|
| Big O (O) | Upper Bound | यह बताता है कि algorithm इससे ज़्यादा time नहीं लेगा, इसलिए इसका इस्तेमाल आमतौर पर worst case के लिए होता है। |
| Omega (Ω) | Lower Bound | यह बताता है कि algorithm इससे कम time नहीं लेगा, इसलिए इसका इस्तेमाल आमतौर पर best case के लिए होता है। |
| Theta (Θ) | Tight Bound | जब upper bound और lower bound एक ही g(n) हों, तब यह algorithm के सटीक growth को बताता है। |
4. Rules for Simplifying Complexity
- Constant multiplier हटा दिया जाता है, जैसे 3n की complexity O(n) लिखी जाती है।
- सिर्फ़ सबसे बड़े order वाला term रखा जाता है, जैसे 5n2 + 3n + 7 की complexity O(n2) होती है।
- एक के बाद एक चलने वाले statements या loops की complexity जोड़ी जाती है, और जोड़ में सबसे बड़ी complexity ही बचती है, जैसे O(n) + O(n2) = O(n2)।
- Loop के अंदर loop हो, तो दोनों की complexity गुणा की जाती है, जैसे O(n) × O(n) = O(n2)।
Order of Growth in Hindi – ग्रोथ का क्रम
Notations में लिखे नतीजों की मदद से algorithms की तुलना की जाती है, और यह तुलना Order of Growth पर आधारित होती है। अलग-अलग algorithms की Time Complexity input size बढ़ने के साथ अलग-अलग रफ़्तार से बढ़ती है। चित्र में कुछ सामान्य complexities के growth की तुलना दिखाई गई है।
सामान्य complexities का क्रम छोटे से बड़े growth की ओर इस प्रकार होता है।
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2^n) < O(n!)
| Complexity | नाम | उदाहरण |
|---|---|---|
| O(1) | Constant | Array के element को index से access करना इसका उदाहरण है। |
| O(log n) | Logarithmic | Sorted array में Binary Search इसका उदाहरण है। |
| O(n) | Linear | Linear Search इसका उदाहरण है। |
| O(n log n) | Linearithmic | Merge Sort इसका उदाहरण है। |
| O(n2) | Quadratic | Bubble Sort और Selection Sort इसके उदाहरण हैं। |
| O(n3) | Cubic | दो n × n matrices का सामान्य तरीके से गुणा करना इसका उदाहरण है। |
| O(2n) | Exponential | Recursive Fibonacci की complexity लगभग इसी के बराबर होती है। |
| O(n!) | Factorial | सभी permutations जाँचने वाले brute-force तरीके इसके उदाहरण हैं। |
