Algorithm Analysis in Hindi | एल्गोरिदम एनालिसिस क्या है

Srajan
⏰ 7 min read

सिलेबस के अनुसार Algorithms के सभी टॉपिक यहाँ देखें — बिल्कुल फ्री

Table of Contents

Algorithm Analysis in Hindi – एल्गोरिदम एनालिसिस क्या है?

Endless Horse – Find End? Play Game
  • Algorithm analysis किसी algorithm की efficiency जाँचने की process है, जिसमें यह पता किया जाता है कि algorithm को चलने के लिए कितना time और कितनी memory चाहिए।
  • एल्गोरिदम एनालिसिस के हिस्सों का चित्र Algorithm + Input size n Algorithm Analysis Time Complexity कितने steps लगे Space Complexity कितनी memory लगी Analysis से algorithm के Time और Space का अनुमान लगाया जाता है
  • इसमें 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 की तुलना कैसे हो।

Algorithm Analysis के हिस्सों के आपसी संबंध का चित्र Algorithm Analysis के हिस्से और उनके सवाल 1. A Priori / A Posteriori Analysis Analysis किस तरीके से किया जाए? 2. Time और Space Complexity Analysis में क्या मापा जाए? 3. Best, Average और Worst Case किस तरह के input पर मापा जाए? 4. Asymptotic Notations नतीजा किस रूप में लिखा जाए? 5. Order of Growth अलग-अलग algorithms की तुलना कैसे हो?
  1. A Priori और A Posteriori Analysis: ये analysis करने के दो तरीके हैं, इसलिए इन्हें Analysis के types कहा जा सकता है।
  2. Time और Space Complexity: ये analysis में मापी जाने वाली दो चीज़ें हैं, इसलिए इन्हें Complexity के types कहा जा सकता है।
  3. Best, Average और Worst Case: ये एक ही algorithm को अलग-अलग inputs पर परखने के तीन तरीके हैं, और हर case में Time और Space दोनों मापे जा सकते हैं।
  4. Asymptotic Notations: ये Time और Space के नतीजे को छोटे और तुलना के लायक रूप में लिखने के संकेत हैं, जैसे T(n) = 3n + 4 को O(n) लिखना।
  5. 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 पर निर्भर)
  1. ऊपर के sum() function में सिर्फ़ s, i और n जैसे कुछ variables चाहिए, इसलिए इसकी Auxiliary Space O(1) है।
  2. किसी array की copy बनाने वाले algorithm में n size का नया array बनता है, इसलिए इसकी Auxiliary Space O(n) है।
  3. 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 से एक-एक करके ढूँढा जाता है।

Linear Search के best case और worst case का चित्र Best Case: key = 8, 1 comparison Worst Case: key = 2, n comparisons 8 3 5 9 2 index 0 index 1 index 2 index 3 index 4 Average Case: key बीच में कहीं भी हो, तो लगभग (n + 1)/2 comparisons
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।
Big O, Omega और Theta notations के graphs का चित्र Big O: f(n) ≤ c·g(n) c·g(n) f(n) n0 Input size n Omega: f(n) ≥ c·g(n) f(n) c·g(n) n0 Input size n Theta: c1·g(n) ≤ f(n) ≤ c2·g(n) c2·g(n) f(n) c1·g(n) n0 Input size n

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 की तुलना दिखाई गई है।

अलग-अलग Time Complexities के growth का चित्र Time Input size n O(log n) O(n) O(n log n) O(n²) O(2^n) n बढ़ने पर अलग-अलग 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 तरीके इसके उदाहरण हैं।

FAQs

Algorithm analysis किसी algorithm की efficiency जाँचने की process है, जिसमें यह पता किया जाता है कि उसे कितना time और कितनी memory चाहिए। इससे एक ही problem के कई algorithms में से सबसे अच्छा algorithm चुना जाता है।
A priori analysis program चलाने से पहले theory के आधार पर किया जाता है और machine पर निर्भर नहीं होता। A posteriori analysis program चलाने के बाद किया जाता है और उसमें असली time और memory नापी जाती है।
Time complexity किसी algorithm को चलने में लगने वाले steps की गिनती है, जिसे input size n के function के रूप में लिखा जाता है। इसे Frequency Count Method से निकाला जाता है और asymptotic notations में लिखा जाता है।
Space complexity किसी algorithm को चलाने के लिए लगने वाली कुल memory है। इसमें Fixed Part और Variable Part होते हैं, और Variable Part में arrays और recursion का call stack जैसी चीज़ें आती हैं।
Best case में algorithm सबसे कम time लेता है, worst case में सबसे ज़्यादा, और average case में सभी inputs पर औसतन जितना time लगता है। Linear Search में best case O(1) और worst case O(n) होता है।
Asymptotic notations वे संकेत हैं जिनसे input size n बहुत बड़ा होने पर algorithm के growth को लिखा जाता है। इनके तीन मुख्य रूप Big O, Omega और Theta हैं।
Big O किसी algorithm के growth की ऊपरी सीमा बताता है। f(n) = O(g(n)) तब होता है जब n ≥ n0 के सभी मानों पर f(n) ≤ c × g(n) हो, जहाँ c और n0 positive constants हैं।
Big O ऊपरी सीमा, Omega निचली सीमा और Theta दोनों के बीच की सटीक सीमा बताता है। यानी Big O में f(n) ≤ c × g(n), Omega में f(n) ≥ c × g(n) और Theta में c1 × g(n) ≤ f(n) ≤ c2 × g(n) होता है।
सामान्य complexities का क्रम छोटे से बड़े growth की ओर O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n) < O(n!) होता है। जिस algorithm की complexity इस क्रम में पहले आती है, वह बड़े input पर तेज़ चलता है।
Algorithm analysis के पाँच हिस्से हैं। A Priori और A Posteriori analysis के तरीके बताते हैं, Time और Space Complexity मापी जाने वाली चीज़ें बताती हैं, Best, Average और Worst Case input का प्रकार बताते हैं, Asymptotic Notations नतीजा लिखने का तरीका बताते हैं और Order of Growth तुलना का आधार देता है।
Srajan

✍️ Srajan

SEO Executive | Content Research & Optimization | 1.5+ Years of Experience

•