जटिलता गणना

Question

क्या है की जटिलता:

int f4(int n) 
{ 
    int i, j, k=1, count = 0; 

    for(i = 0; i < n; i++) 
    { 
     k *= 3; 

     for(j = k; j; j /= 2) 
     count++; 
    } 

    return count; 
} 

मैं जानता हूँ कि यह है O (n^2), लेकिन आप इस गणना कैसे करते हैं? और यह एन * लॉग एन क्यों नहीं है?

Answer 1

एन बाहरी लूप हैं। किसी भी बिंदु पर, k = 3i। वहाँ log2(k) भीतरी लूप बने हैं (क्योंकि हम प्रत्येक यात्रा पर j आधा करना।)

log2(3i) = log3 (3i)/log3(2) = i/(constant)

तो भीतरी पाश की जटिलता i है। दूसरे शब्दों में, इस कार्यक्रम के रूप में

int f4changed(int n) 
{ 
    int i, j, count = 0; 

    for(i = 0; i < n; i++) 
    { 
     for(j = 0; j < i; j++) 
     { 
      count++; 
     } 
    } 
} 

ही जटिलता (लेकिन ठीक उसी पुनरावृत्तियों की संख्या) यह O(n2)as you've already seen है।

Answer 2

मैं = 1 3 पुनरावृत्तियों में परिणाम (भीतरी पाश की) (3, 1, 0)
मैं = 2 8 (5 तो 3)
मैं = 3 है 13 (7 + 5 + 3) है

आपके पास arithmetic series का अनुमान है, जो ओ (एन) है।

पूर्णता के लिए (और यह समझाने के लिए कि पुनरावृत्ति की सटीक संख्या क्यों मायने रखती है), Plain english explanation of Big O देखें (यह आपके पाठकों के लिए अधिक है, पोस्टर के बाद से आप जानते हैं कि क्या हो रहा है)।

Answer 3

लॉग की जटिलता (पॉव (3, एन)) ~ ओ (एन)। यदि आंतरिक पाश के * = 2 था, तो पुनरावृत्तियों की संख्या भी एन होगी।
ओ (~) की गणना के लिए उच्चतम शक्ति शब्द का उपयोग किया जाता है और अन्य उपेक्षित होते हैं। लॉग (पॉव (3, एन)) को
लॉग (पॉव (2, एन)) < = लॉग (पॉव (3, एन)) < = लॉग (पॉव (4, एन))
अब लॉग (पॉव (4, एन)) = 2 * लॉग (पॉव (2, एन))।

यहां उच्चतम ऊर्जा अवधि एन है (जैसा कि 2 स्थिर है)।