रिकर्सन फ़ंक्शन के लिए बिग ओ

Question

मुझे पता है कि जब आप किसी निर्दिष्ट अंश में सेट की गई समस्या के आकार को विभाजित करते हैं तो आप ओ (लॉग (एन)) से निपट रहे हैं। हालांकि मैं उलझन में हूं जब वे अधिक 1 रिकर्सिव कॉल करते हैं जो ऐसा करते हैं। उदाहरण के लिए यहां इस समारोह में हम एक एक्सपोनेंट के मूल्य की गणना करने जा रहे हैं।

public static long pow(long x, int n) 
    { 
     if(n==1) 
     return x; 
     if(isEven(n)) 
     return pow(x,n/2) * pow(x,n/2); 
     else 
     return pow(x*x, n/2) * x 
     } 

विश्लेषण करने के बाद, मुझे रन टाइम ओ (एन) के बराबर मिला। क्या मैं सही हूँ? आपके समय के लिए धन्यवाद

Answer 1

हां, आप कम से कम सबसे खराब केस विश्लेषण के तहत सही हैं।

ध्यान दें कि n = 2^k के लिए, कुछ प्राकृतिक k के लिए, आपको लगता है कि स्टॉप क्लॉज तक पहुंचने के अलावा, स्थिति हमेशा सत्य होती है, और रिकर्सिव फ़ंक्शन दो बार भाग जाएगा।

जब कि स्थापित है, यह विश्लेषण करने के लिए पर्याप्त है:

T(n) = T(n/2) + T(n/2) + X 

कहाँ X कुछ स्थिर है, (प्रत्येक पुनरावर्ती कॉल, काम की लगातार राशि लेता है, तो अन्य पुनरावर्ती कॉल की अनदेखी)।

master theorem case 1 से

, साथ:

f(n) = X 
a = 2, b = 2, c = 0 (since X is in O(n^0)=O(1)) 

और c=0 < 1 = log_2(2) के बाद से, मामले 1 के लिए शर्तें लागू होती हैं, और हम में समारोह T(n) है निष्कर्ष निकाल सकते हैं Theta(n^log_2(2)) = Theta(n)

औसत मामले विश्लेषण:

औसत मामले के लिए, समान रूप से वितरित संख्या n के साथ, द्विआधारी प्रतिनिधित्व में बिट्स का आधा इस संख्या का आयन (1) होगा, और आधा 'नीचे' (0) होगा।

2 से विभाजित के बाद से मूल रूप से गणित पारी सही है, और यदि और केवल यदि कम से कम महत्वपूर्ण बिट 0 है, इसका मतलब है इसका मतलब यह जटिलता समारोह है हालत isEven(n) सत्य है:

T(n) = 0.5 T(n/2) + 0.5 * 2 T(n/2) + X = 0.5 * 3 * T(n/2) + X 
    = 1.5 * T(n/2) + X 

तो

एक = 3/2, ख = 2, सी = 0

:

T(n) = 3/2 T(n/2) + X 

केस 1 अभी भी (यह मानते हुए निरंतर X) लागू होता है

यह वास्तव में सभी arithmetics O(1) हैं मान लिया गया है:

और आप की Theta(n^log_1.5(2))~=Theta(n^0.58)

त्वरित नोट औसत मामले जटिलता मिलता है। यदि यह मामला नहीं है (बहुत बड़ी संख्या), तो आपको T(n) की परिभाषा में निरंतर की बजाय अपनी जटिलता डालना चाहिए, और पुन: विश्लेषण करना चाहिए। इस तरह के प्रत्येक ऑपरेशन को मानना ​​उप-रैखिक है (संख्या में, इसका प्रतिनिधित्व करने वाली बिट्स नहीं), परिणाम Theta(n) रहता है, क्योंकि मास्टर प्रमेय के मामले 1 अभी भी लागू होते हैं। (औसत मामले के लिए, किसी भी फ़ंक्शन के लिए से बेहतर "

Answer 2

वरुण, आप आंशिक रूप से सही हैं।चलो दो मामलों देखें:

1. n भी है, तो आप सिर्फ काम दो हिस्सों में काफी अनुकूलन किए बिना, विभाजित कर रहे हैं रहा है, तो के बाद से pow(x, n/2) दो बार गणना की जाती है।

2. यदि n अजीब है, तो आपके पास अपघटन का एक विशेष मामला है। x को x x द्वारा प्रतिस्थापित किया जाएगा, जो x x नया आधार बनाता है, जो आपको x * x को पुन: गणना करने से बचाता है।

पहले मामले में हम, क्योंकि यह आसान है पूरी बात कर रही है की तुलना में छोटे प्रस्तुतियों को दोहराने के लिए, एक मामूली अनुकूलन है के रूप में:

(3 * 3 * 3 * 3) * (3 * 3 * 3 * 3) की तुलना में गणना की जा सकती है (3 * 3 * 3 * 3 * 3 * 3 * 3 * 3), इसलिए पहला मामला इस तथ्य का उपयोग करके गणना में थोड़ा सुधार करता है कि उत्पादन एक सहयोगी ऑपरेशन है। पहले मामले में निष्पादित उत्पादन की संख्या कम नहीं हुई है, लेकिन गणना के तरीके के तरीके बेहतर है।

हालांकि, दूसरे मामले में, आपके पास महत्वपूर्ण अनुकूलन हैं। मान लें कि n = (2^p) - 1। उस स्थिति में, हम समस्या को किसी समस्या पर कम करते हैं, जहां n = ((2^p - 1) - 1)/2 = ((2^p) - 2)/2 = (2^(p-1)) - 1। इसलिए, यदि पी एक प्राकृतिक संख्या है और n = (2^p) - 1 है, तो आप इसे अपने आधा तक कम कर रहे हैं। इसलिए, एल्गोरिदम सबसे अच्छा केस परिदृश्य n = (2^p) - 1 में लॉगरिदमिक है और यह सबसे खराब स्थिति परिदृश्य n = 2^p में रैखिक है।

Answer 3

हम आमतौर पर सबसे खराब केस टाइम जटिलता का विश्लेषण करते हैं, जो तब होता है जब भी (एन) सत्य होता है। उस स्थिति में, हमारे पास

T(n) = 2T(n/2) + O(1) 

जहां टी (एन) का अर्थ पाउ (x, n) की जटिलता है।

टी (एन) के बिग-ओ नोटेशन फॉर्म को प्राप्त करने के लिए Master theorem, Case 1 लागू करें। यही कारण है:

T(n) = O(n)