Time Complexity in Hindi

समय जटिलता = इनपुट का आकार (n) बढ़ने पर एल्गोरिदम को हल करने में कितना समय लगेगा।

समय जटिलता को सामान्यतः तीन रूपों में मापा जाता है:

टाइम कॉम्प्लेक्सिटी को दर्शाने के लिए बिग-ओ नोटेशन का उपयोग किया जाता है। यह हमें बताता है कि इनपुट का आकार बढ़ने पर एल्गोरिदम की निष्पादन समय किस प्रकार से बढ़ेगा।

Big-O Notation में, हम केवल सबसे महत्वपूर्ण समय जटिलता की गणना करते हैं। इसका मतलब है कि छोटे कारक (जैसे स्थिरांक या छोटे क्रम के कारक) को नजरअंदाज किया जाता है।

उदाहरण:

यदि एल्गोरिदम की समय जटिलता 

2

𝑛

2

+

3

𝑛

+

5

2n 

2

 +3n+5 है, तो इसे बिग-ओ नोटेशन में 

𝑂

(

𝑛

2

)

O(n 

2

 ) लिखा जाएगा, क्योंकि 

𝑛

2

n 

2

  सबसे प्रमुख कारक है।

O(1) - कॉन्स्टेंट टाइम कॉम्प्लेक्सिटी (Constant Time Complexity):

जब एल्गोरिदम का निष्पादन समय इनपुट के आकार पर निर्भर नहीं करता और हमेशा एक निश्चित समय में समाप्त हो जाता है, तो इसे O(1) कहा जाता है। यह सबसे कुशल समय जटिलता मानी जाती है।

उदाहरण:

int getFirstElement(int arr[], int n) {

    return arr[0];  // केवल पहले तत्व तक पहुँचना

}

इस एल्गोरिदम में, चाहे ऐरे का आकार कितना भी बड़ा हो, यह केवल पहले तत्व तक पहुँचता है। इसलिए, इसका समय O(1) है।

जब एल्गोरिदम का निष्पादन समय इनपुट के आकार n के सीधे अनुपात में बढ़ता है, तो इसे O(n) कहा जाता है। इसका मतलब है कि जैसे-जैसे इनपुट का आकार बढ़ता है, निष्पादन समय उसी अनुपात में बढ़ता है।

उदाहरण:

int sumArray(int arr[], int n) {

    int sum = 0;

    for (int i = 0; i < n; i++) {

        sum += arr[i];  // सभी तत्वों का योग

    }

    return sum;

}

इस एल्गोरिदम में, ऐरे के सभी तत्वों को एक-एक करके एक्सेस किया जाता है, इसलिए इसका समय O(n) है।

जब एल्गोरिदम का निष्पादन समय इनपुट के आकार n के वर्ग (n²) के अनुपात में बढ़ता है, तो इसे O(n²) कहा जाता है। यह तब होता है जब एल्गोरिदम में दो घोंसले वाले लूप (Nested Loops) होते हैं।

उदाहरण:

void printAllPairs(int arr[], int n) {

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            printf("%d, %d\n", arr[i], arr[j]);  // प्रत्येक तत्व का हर दूसरे तत्व के साथ जोड़ा बनाना

        }

    }

}

इस एल्गोरिदम में दो लूप हैं, और प्रत्येक लूप n बार चलता है। इसलिए, इसकी समय जटिलता O(n²) है।

जब एल्गोरिदम का निष्पादन समय इनपुट के आकार के लोगरिद्मिक अनुपात में बढ़ता है, तो इसे O(log n) कहा जाता है। लोगरिद्मिक समय तब उत्पन्न होता है जब इनपुट के आकार को प्रत्येक स्टेप में आधा कर दिया जाता है।

उदाहरण:

int binarySearch(int arr[], int n, int key) {

    int low = 0, high = n - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        if (arr[mid] == key) return mid;

        else if (arr[mid] < key) low = mid + 1;

        else high = mid - 1;

    }

    return -1;

}

बाइनरी सर्च में हर बार इनपुट के आकार को आधा कर दिया जाता है, इसलिए इसकी समय जटिलता O(log n) है।

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

उदाहरण: मर्ज सॉर्ट और क्विक सॉर्ट जैसे एल्गोरिदम की समय जटिलता O(n log n) होती है।

जब एल्गोरिदम का निष्पादन समय इनपुट के आकार के आधार पर 2 की शक्ति के रूप में बढ़ता है, तो इसे O(2^n) कहा जाता है। यह बहुत धीमी समय जटिलता होती है और बड़े इनपुट्स के लिए उपयुक्त नहीं होती।

उदाहरण:

int fibonacci(int n) {

    if (n <= 1) return n;

    return fibonacci(n - 1) + fibonacci(n - 2);  // पुनरावर्ती ढंग से फिबोनाची संख्या का निर्धारण

}

इस एल्गोरिदम में समय जटिलता O(2^n) होती है, क्योंकि प्रत्येक फिबोनाची संख्या की गणना के लिए कई पुनरावृत्तियाँ की जाती हैं।