Understanding Space Complexity in DSA

If tutorials available on this website are helpful for you, please whitelist this website in your ad blocker😭 or Donate to help us ❤️ pay for the web hosting to keep the website running.

Space Complexity एक important concept है जो Data Structures and Algorithms (DSA) में use होता है। अगर आप programming सीख रहे हैं या already सीख चुके हैं, तो आपको space complexity समझना जरूरी है।

आज हम simple examples के through space complexity को समझेंगे, ताकि आप इस concept को अच्छे से grasp कर सकें।

●●●

Space Complexity क्या है?

जब हम किसी algorithm को run करते हैं, तो उस algorithm को अपने operations execute करने के लिए कुछ memory कि need होती है। यह memory consumption को हम space complexity कहते हैं।

Space complexity के through हम यह जान सकते हैं कि algorithm को run करते वक्त कितन memory कि need होगी।

मतलब, अगर आप एक algorithm लिख रहे हैं, तो space complexity आपको बताता है कि उस algorithm को कितना memory space चाहिए होगा, जिसे आप as a programmer efficiently manage कर सकें।

Formula of Space Complexity

Space complexity को usually Big O notation के through express किया जाता है, यह notation यह बताता है कि किसी algorithm कि space requirement का growth किस तरह से बढ़ेगी जब input size increase होगा।

For example :

• O(1): Constant space

• O(n): Linear space

• O(n^2): Quadratic space

• Other

Space Complexity को कैसे Calculate करें?

जब आप किसी algorithm को लिखते हैं, तो आपको यह देखना होता है कि आपके algorithm में किस तरह का data structures use हो रहे हैं। इसके अलावा , recursive calls भी memory consume करते हैं।

चलिए, अब हम PHP और JavaScript के simple examples के through समझते हैं।

●●●

Space Complexity Example

Copy
function sumArray(arr) {
    let sum = 0; // O(1) space

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

    return sum;
}

let arr = [1, 2, 3, 4, 5];
console.log(sumArray(arr));

इस example में:

• हमने एक array बनाया और उसके elements का sum निकलने के लिए एक loop चलाया।

• यहाँ पर space complexity O(1) है क्योंकि हम सिर्फ एक sum variable को store कर रहे हैं। चाहेarray कितना भी बड़ा हो, हमारी memory usage change नहीं होती। 

• सिर्फ एक variable कि need है।
  

Recursive Function Example

अगर आप recursion use करते हैं, तो space complexity थोड़ा complex हो सकता है।

जैसे -

Copy
function factorial(n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

console.log(factorial(5));  
// Output: 120

इस example में :

• Recursive calls कि वजह से stack memory का use हो रहा है।

• अगर n = 5 है, तो 5 recursive calls stack में store होते हैं। 

• यहाँ space complexity O(n) होगी, क्योंकि function stack में हर call को store करता है जब तक base case नहीं मिलता।
  

●●●

Importance of Space Complexity

Space complexity कि understanding इसलिए जरूरी है, क्योंकि अगर आप का code efficient नहीं है, तो आपका program बहुत ज़्यादा memory consume करेगा, जो performance को impact करेगा।

Large input sizes के case में memory hogging से program slow या crash भी कर सकता है।

Space Complexity के Examples:

1. O(1) – Constant Space 

• आपका program किसी भी extra memory को allocate नहीं करता, सिर्फ fixed-size variables को store करता है।

• Example: Simple loops या mathematical operations.

2. O(n) – Linear Space

• आप program में array या list का use करते हैं, जिसमे input size के according से memory allocate होती है।

• Example: Array या list का use करके data store करना।
  

3. O(n^2) – Quadratic Space

• अगर आप 2D arrays या matrices use कर रहे हैं, तो memory requirement square of n होता है।

• Example: Matrix multiplication.

●●●

Conclusion

तो space complexity एक ऐसे concept है जो आपको बताना है कि आपका program कितना memory consume करेगा। आप जब DSA के problems solve करते हैं, तो space complexity का ध्यान रखना जरूरी होता है।

इससे आपके program का efficiency और performance दोनो improve होता है।