Big-O नोटेशन: स्पेस कॉम्प्लेक्सिटी

Java में कोड ऑप्टिमाइज़ करना

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

स्पेस कॉम्प्लेक्सिटी क्या है?

टाइम कॉम्प्लेक्सिटी बताती है कि इनपुट साइज runtime{{1}} को कैसे प्रभावित करता है
स्पेस कॉम्प्लेक्सिटी बताती है कि इनपुट साइज memory usage{{2}} को कैसे प्रभावित करता है

स्पेस कॉम्प्लेक्सिटी समझना उन ऐप्लिकेशनों के लिए ज़रूरी है जो:

बस उतनी ही मेमोरी लें जितनी चाहिए, उससे ज़्यादा नहीं
OutOfMemoryError जैसी त्रुटियों से बचें

Big-O नोटेशन

नोटेशन टाइम कॉम्प्लेक्सिटी जैसा ही है।

कुछ आम कॉम्प्लेक्सिटी क्लास:

O(1): Constant time - साइज से स्वतंत्र
O(n): Linear time - इनपुट साइज के साथ बढ़ता है
O(n²): Quadratic time - इनपुट साइज के वर्ग के साथ बढ़ता है

मैक्सिमम खोजने की मेथड

public int findMax(int[] array) {
    int max = Integer.MIN_VALUE;
    for (int value : array) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

चाहे हमारे integer array में 10 हों या 10 million एलिमेंट, हम फिर भी केवल एक वैरिएबल max के लिए मेमोरी लेते हैं
स्पेस कॉम्प्लेक्सिटी O(1) या constant space है

डबलिंग मेथड

public int[] doubleValues(int[] array) {
    int[] result = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        result[i] = array[i] * 2;
    }
    return result;
}

अगर इनपुट में n एलिमेंट हैं, तो हमें n अतिरिक्त एलिमेंट के लिए स्पेस चाहिए
स्पेस कॉम्प्लेक्सिटी O(n) है क्योंकि अतिरिक्त मेमोरी इनपुट साइज के साथ रैखिक रूप से बढ़ती है

मल्टिप्लिकेशन टेबल मेथड

public int[][] multiplicationTable(int n) {
    int[][] table = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            table[i][j] = (i + 1) * (j + 1);
        }
    }
    return table;
}

अगर n 10 है, तो 100 सेल चाहिए; अगर n 100 है, तो 10,000 सेल चाहिए
हम इसे O(n²) के रूप में वर्गीकृत करते हैं

स्पेस कॉम्प्लेक्सिटी क्यों महत्वपूर्ण है?

मेमोरी सीमित संसाधन है!

पिछले उदाहरण, 10,000 एलिमेंट के इनपुट पर:

findMax, O(1) -> बस कुछ अतिरिक्त bytes
doubleValues, O(n) -> लगभग 40KB अतिरिक्त मेमोरी
multiplicationTable, O(n²) -> लगभग 400MB अतिरिक्त मेमोरी

बार प्लॉट: findMax में 8 byte, doubleValues में 40KB, और multiplicationTable में 400MB मेमोरी बढ़ोतरी दिखती है

स्पेस कॉम्प्लेक्सिटी बनाम टाइम कॉम्प्लेक्सिटी

याद रखें:

कभी-कभी हम समय के बदले स्पेस लेते हैं
कभी-कभी स्पेस के बदले समय लेते हैं
सही चुनाव आपकी विशेष constraints पर निर्भर है

ग्राफ़िक: समय और स्पेस के बीच trade-off को दर्शाता है

अभ्यास करते हैं!

Java में कोड ऑप्टिमाइज़ करना