हल करें: टी (एन) = टी (एन/2) + एन/2 + 1

Question

मैं ओ नोटेशन में निम्नलिखित एल्गोरिदम के लिए चलने वाले समय को परिभाषित करने के लिए संघर्ष करता हूं। मेरा पहला अनुमान ओ (एन) था, लेकिन पुनरावृत्तियों और लागू होने वाले नंबर के बीच का अंतर स्थिर नहीं है। मैंने इसे गलत तरीके से कैसे परिभाषित किया है?

public int function (int n) 
{ 
    if (n == 0) { 
    return 0; 
    } 

    int i = 1; 
    int j = n ; 
    while (i < j) 
    { 
    i = i + 1; 
    j = j - 1; 
    } 
    return function (i - 1) + 1; 
} 

Answer 1

whilen/2 के बारे में समय पर निष्पादित किया जाता है।

प्रत्यावर्तन n के रूप में मूल n का केवल आधा है कि एक मूल्य गुजर रहा है निष्पादित, तो:

n/2 (first iteration) 
n/4 (second iteration, equal to (n/2)/2) 
n/8 
n/16 
n/32 
... 

यह एक geometric serie के समान है।

दरअसल के रूप में

n * (1/2 + 1/4 + 1/8 + 1/16 + ...) 

तो यह n * 1 = n

को अभिमुख यह दर्शाया जा सकता है तो हे संकेतन हे (एन)

Answer 2

एक और दृष्टिकोण है यह T(n) = T(n/2) + n/2 + 1 के रूप में लिखने के लिए नीचे है ।
जबकि लूप n/2 काम करता है। अगली कॉल में पास किया गया तर्क n/2 है।

• एक = 1
• ख = 2
• च = n/2 + 1

:

master theorem जहां का उपयोग कर इस को सुलझाने

Let c=0.9 
1*(f(n/2) + 1) <? c*f(n) 
1*(n/4)+1 <? 0.9*(n/2 + 1) 
0.25n + 1 <? 0.45n + 0.9 
    0 < 0.2n - 0.1 

कौन सा है:

T(n) = Θ(n)