आप इस एल्गोरिदम की औसत-केस जटिलता को कैसे निर्धारित करते हैं?

Question

सर्वोत्तम मामले और सबसे बुरे मामले के लिए समय जटिलता की गणना करना आम तौर पर आसान होता है, लेकिन जब औसत मामले की बात आती है, खासकर जब कोई संभावना पी होती है, तो मुझे नहीं पता कि कहां से शुरू करना है।

के एक मैट्रिक्स में सभी तत्वों के उत्पाद की गणना करने के निम्नलिखित कलन विधि पर नजर डालते हैं:

int computeProduct(int[][] A, int m, int n) { 
    int product = 1; 
    for (int i = 0; i < m; i++ { 
     for (int j = 0; j < n; j++) { 
      if (A[i][j] == 0) return 0; 
      product = product * A[i][j]; 
     } 
    } 
    return product; 
} 

मान लीजिए पी A[i][j] जा रहा है 0 की संभावना है (यानी एल्गोरिथ्म वहाँ समाप्त हो जाता है, लौटने 0) है; हम इस एल्गोरिदम के लिए औसत केस टाइम जटिलता कैसे प्राप्त करते हैं?

Answer 1

चलो एक संबंधित समस्या पर विचार करें। कल्पना कीजिए कि आपके पास एक सिक्का है जो संभावना पी के साथ सिर फिसलता है। कितनी बार, उम्मीद पर, क्या आपको सिर आने से पहले सिक्के को फ़्लिप करने की ज़रूरत है? जवाब 1/पी है, क्योंकि

• एक पी संभावना है कि आपको एक फ्लिप की आवश्यकता है।
• एक पी (1-पी) मौका है कि आपको दो फ्लिप की आवश्यकता है (पहली फ्लिप को पूंछ जाना है और दूसरे को सिर जाना है)।
• है एपी (1-पी)^2 संभावना है कि आप तीन flips की जरूरत है (पहले दो flips पूंछ जाने की जरूरत है और तीसरे सिर जाना पड़ता है)
• ...
• है एपी (1-पी)^(के -1) मौका है कि आपको के फ्लिप की आवश्यकता है (पहले के -1 फ्लिप्स को पूंछ जाने की जरूरत है और केटी को सिर जाने की जरूरत है।)

तो इसका मतलब है फ्लिप की संख्या का अनुमानित मूल्य है

p + 2p (1 - पी) + 3p (1 - पी)^2 + 4P (1 - पी)^3 + ...

= पी (1 (1 - पी)^0 + 2 (1 - पी)^1 + 3 (1 - पी)^2 + ...)

तो अब हम बाहर काम करने की जरूरत है यह सारांश क्या है। सामान्य रूप

पी = 1 से अनंतता (के (1 - पी)^के) से योग राशि है।

इस विशेष सारांश को हल करने के बजाय, इसे और अधिक सामान्य बनाएं। एक्स को कुछ वैरिएबल होने दें, बाद में, हम 1 - पी के बराबर सेट करेंगे, लेकिन अब के लिए हम एक मुफ्त मूल्य के रूप में व्यवहार करेंगे। फिर हम उपरोक्त सारांश को

पी = 1 से अनंत तक (kx^(k-1)) के रूप में पुनः लिख सकते हैं।

अब एक सुंदर चाल के लिए: ध्यान दें कि इस अभिव्यक्ति के अंदर x के संबंध में x^k का व्युत्पन्न है। इसलिए, यह योग

पी = 1 से अनंत तक (डी/डीएक्स x^के) योग राशि है।

व्युत्पन्न एक रेखीय ऑपरेटर है, इसलिए हम सामने के लिए बाहर ले जा सकते हैं: कश्मीर से = 1 अनंत को

पीडी/dx राशि (x^ट)

यही कारण है कि भीतरी राशि (x + x^2 + x^3 + ...) के लिए 1/टेलर श्रृंखला है (1 - x) - 1, इसलिए हम इस आसान बनाने

पीडी/dx प्राप्त करने के लिए कर सकते हैं (1/(1 - एक्स) - 1)

= पी/(1 - एक्स)^2

और हम उठाया के बाद से एक्स = 1 - पी, इस

को सरल करता है

पी/(1 - (1 - पी))^2

= पी/पी^2

= 1/p

वाह! वह एक लंबा व्युत्पन्न था। लेकिन यह दिखाता है कि सिक्का टॉस की अपेक्षित संख्या 1/पी है।

अब, आपके मामले में, आपके एल्गोरिदम को एमएन सिक्कों को फेंकने के बारे में सोचा जा सकता है जो संभावना पी के साथ सिर आते हैं और उनमें से कोई भी सिर ऊपर आ जाता है। निश्चित रूप से, आपको टॉस करने की आवश्यकता वाले सिक्कों की अपेक्षित संख्या उस मामले से अधिक नहीं होगी जहां आपको असीमित रूप से फ़्लिप करने की अनुमति है, इसलिए आपका अपेक्षित रनटाइम अधिकांश ओ (1/पी) (पी> 0 मानते हुए) ।

यदि हम मानते हैं कि पी एम और एन से स्वतंत्र है, तो हम देख सकते हैं कि कुछ शुरुआती विकास के बाद, हमारे सारांश में प्रत्येक जोड़ा शब्द, क्योंकि हम फ्लिप की संख्या को बढ़ाते हैं, पिछले की तुलना में तेजी से कम है। अधिक विशेष रूप से, योग में मोटे तौर पर लॉगरिदमिक रूप से कई शर्तों को जोड़ने के बाद हम अनंत सारांश के मामले में कुल से बंद हो जाएंगे। इसलिए, बशर्ते कि एमएन Θ (लॉग पी) से लगभग बड़ा है, योग Θ (1/पी) होने पर समाप्त होता है। तो एक बड़े-ओ अर्थ में, यदि एमएन पी से स्वतंत्र है, तो रनटाइम Θ (1/पी) है।