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

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

Pavlos Kosmetatos

Lead Engineer @Wealthyhood

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

टाइम कॉम्प्लेक्सिटी: इनपुट बढ़ने पर रनटाइम कैसे बढ़ता है
यह सवाल सुलझाने में मदद: "जब मेरा डेटा 10× हो जाए तो क्या होगा?"
ऐब्सोल्यूट समय पर फोकस नहीं करता

Big-O नोटेशन

वर्स्ट-केस समझाने की गणितीय नोटेशन.

कुछ सामान्य कॉम्प्लेक्सिटी क्लासेज:

O(1): कॉन्स्टेंट टाइम - साइज-इंडिपेंडेंट

O(1) को समझना

O(1) ऑपरेशन का एक उदाहरण ArrayList का get() है

Strings रखने वाले ArrayList का आंतरिक (सरल) इम्प्लीमेंटेशन:

public class ArrayList {}
    private String[] data; // Internal array
    private int size;

    // Get operation - direct array access
    public String get(int index) {
        return data[index]; // O(1)
    }
}

Big-O नोटेशन

वर्स्ट-केस समझाने की गणितीय नोटेशन

कुछ सामान्य कॉम्प्लेक्सिटी क्लासेज:

O(1): कॉन्स्टेंट टाइम - साइज-इंडिपेंडेंट
O(n): लीनियर टाइम - इनपुट के साथ बढ़ता है

O(n) को समझना

इसी तरह का उदाहरण, पर ArrayList के contains() के लिए

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    // Linear search through array
    for (int i = 0; i < size; i++) {
        if (o.equals(elementData[i])) {
            return i;
        }
    }
    return -1; // Not found
}

Big-O नोटेशन

वर्स्ट-केस समझाने की गणितीय नोटेशन

कुछ सामान्य कॉम्प्लेक्सिटी क्लासेज:

O(1): कॉन्स्टेंट टाइम - साइज-इंडिपेंडेंट
O(n): लीनियर टाइम - इनपुट के साथ बढ़ता है
O(n²): क्वाड्रेटिक टाइम - इनपुट के साथ वर्गानुपाती बढ़ता है

क्वाड्रेटिक कॉम्प्लेक्सिटी का व्यावहारिक उदाहरण

// ऐसी संख्या-जोड़ी ढूँढना जिनका योग target के बराबर हो
// Time complexity: O(n²)

public int[] findPairWithSum(ArrayList<Integer> numbers, int targetSum) {
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            if (numbers.get(i) + numbers.get(j) == targetSum) {
                console.log("Found them!")
            }
        }
    }
}

टाइम कॉम्प्लेक्सिटी क्यों मायने रखती है

इनपुट साइज का असर:

O(1): 1,000 -> 1,000,000 आइटम = समय समान!
O(n): 1,000 -> 1,000,000 आइटम = 1,000× धीमा
O(n²): 1,000 -> 1,000,000 आइटम = 1,000,000× धीमा

Screenshot 2025-05-10 at 2.27.06 PM.png

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

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