इस फ़ंक्शन (f1) की समय जटिलता क्या है?

जैसा कि मैं देख सकता हूं कि पहला लूप (i = 0) -> (n / 4 बार) दूसरा वाला (i = 3) -> (n / 4 - 3 बार) .... आदि, परिणाम है: ( n/3)*(n/4 + (n-3)/4 + (n-6)/4 + (n-9)/4 ....

और मैं यहीं रुकता हूं, कैसे जारी रखूं?

int f1(int n){
  int s=0;
  for(int i=0; i<n; i+=3)
    for (int j=n; j>i; j-=4)
      s+=j+i;
  return s;
}
0
sam0101 6 अक्टूबर 2018, 01:47

3 जवाब

सबसे बढ़िया उत्तर

बिग (ओ) अंकन के बारे में महत्वपूर्ण बात यह है कि यह 'स्थिरांक' को समाप्त करता है। इसका उद्देश्य रुझान को निर्धारित करना है क्योंकि विशिष्ट संख्याओं की चिंता किए बिना इनपुट आकार बढ़ता है।

इसे एक ग्राफ पर वक्र का निर्धारण करने के रूप में सोचें जहां आप x और y अक्षों की संख्या श्रेणियों को नहीं जानते हैं।

तो आपके कोड में, भले ही आप प्रत्येक लूप के प्रत्येक पुनरावृत्ति के लिए n की सीमा में अधिकांश मानों को छोड़ दें, यह स्थिर दर पर किया जाता है। तो इस बात की परवाह किए बिना कि आप वास्तव में कितने छोड़ते हैं, यह अभी भी n^2 के सापेक्ष है।

यदि आप निम्न में से किसी की गणना करते हैं तो इससे कोई फर्क नहीं पड़ेगा:

1/4 * n^2
0.0000001 * n^2
(1/4 * n)^2
(0.0000001 * n)^2
1000000 + n^2
n^2 + 10000000 * n

बिग ओ में, ये सभी O(n^2) के बराबर हैं। बात यह है कि एक बार n बड़ा हो जाता है पर्याप्त (जो कुछ भी हो), सभी निचले क्रम की शर्तें और स्थिर कारक 'बड़ी तस्वीर' में अप्रासंगिक हो जाते हैं।

(यह ध्यान देने योग्य है कि यही कारण है कि छोटे इनपुट पर आपको बिग ओ पर बहुत अधिक भरोसा करने से सावधान रहना चाहिए। यही कारण है कि लगातार ओवरहेड्स का अभी भी एक बड़ा प्रभाव हो सकता है।)

3
user10461681user10461681 6 अक्टूबर 2018, 03:11

मुख्य अवलोकन: आंतरिक लूप चरण i में (n-i)/4 बार निष्पादित होता है, इसलिएi/4 चरण n-i में।

अब इन सभी राशियों को i = 3k, 3(k-1), 3(k-2), ..., 9, 6, 3, 0 के लिए जोड़ दें, जहां 3k, n (यानी, 3k <= n < 3(k+1)) से पहले 3 का सबसे बड़ा गुणज है:

3k/4 + 3(k-1)/4 + ... + 6/4 + 3/4 + 0/4 = 3/4(k + (k-1) + ... + 2 + 1)
                                        = 3/4(k(k+1))/2
                                        = O(k^2)
                                        = O(n^2)

क्योंकि k <= n/3 <= k+1 और इसलिए k^2 <= n^2/9 <= (k+1)^2 <= 4k^2

1
Leandro Caniglia 6 अक्टूबर 2018, 14:24

सिद्धांत रूप में यह "ओ (एन * एन)" है, लेकिन ...

क्या होगा यदि संकलक इसे इसमें अनुकूलित करने जैसा महसूस करता है:

int f1(int n){
  int s=0;
  for(int i=0; i<n; i+=3)
    s += table[i];
  return s;
}

या यह भी:

int f1(int n){
  if(n <= 0) return 0;
  return table[n];
}

फिर यह "ओ (एन)" या "ओ (1)" भी हो सकता है।

ध्यान दें कि सतह पर इस प्रकार के अनुकूलन अव्यावहारिक लगते हैं (सबसे खराब स्थिति स्मृति लागत के कारण); लेकिन पर्याप्त रूप से उन्नत कंपाइलर के साथ (उदाहरण के लिए सभी कॉलर्स की जांच करने के लिए "संपूर्ण प्रोग्राम ऑप्टिमाइज़ेशन" का उपयोग करना और यह निर्धारित करना कि n हमेशा एक निश्चित सीमा के भीतर है) यह समझ से बाहर नहीं है। इसी तरह सभी कॉल करने वालों के लिए एक स्थिरांक का उपयोग करना असंभव नहीं है (उदाहरण के लिए जहां एक पर्याप्त उन्नत कंपाइलर x = f1(123); जैसी चीजों को x = constant_calculated_at_compile_time से बदल सकता है)।

दूसरे शब्दों में; व्यवहार में, मूल फ़ंक्शन की समय जटिलता इस बात पर निर्भर करती है कि फ़ंक्शन का उपयोग कैसे किया जाता है और कंपाइलर कितना अच्छा/बुरा है।

-1
Brendan 6 अक्टूबर 2018, 06:11