इस एल्गोरिदम की समय जटिलता

Question

एक ऐसा प्रोग्राम लिखें जो एक पूर्णांक लेता है और मूल संख्या के बराबर छोटे पूर्णांक को गुणा करने के सभी तरीकों को मुद्रित करता है, बिना कारकों के सेट दोहराए। दूसरे शब्दों में, यदि आपके आउटपुट में 4 * 3 है, तो आपको फिर से 3 * 4 प्रिंट नहीं करना चाहिए क्योंकि यह एक दोहराना सेट होगा। ध्यान दें कि यह केवल प्रमुख कारक के लिए नहीं पूछ रहा है। साथ ही, आप मान सकते हैं कि इनपुट पूर्णांक आकार में उचित हैं; दक्षता की तुलना में शुद्धता अधिक महत्वपूर्ण है। PrintFactors (12) 12 * 1 6 * 2 4 * 3 3 * 2 * 2

public void printFactors(int number) { 
    printFactors("", number, number); 
} 

public void printFactors(String expression, int dividend, int previous) { 
    if(expression == "") 
     System.out.println(previous + " * 1"); 

    for (int factor = dividend - 1; factor >= 2; --factor) { 
     if (dividend % factor == 0 && factor <= previous) { 
      int next = dividend/factor; 
      if (next <= factor) 
       if (next <= previous) 
        System.out.println(expression + factor + " * " + next); 

      printFactors(expression + factor + " * ", next, factor); 
     } 
    } 
} 

मुझे लगता है, यह

दी गई संख्या एन और के एन = घ प्रधानमंत्री कारकों की संख्या है, तो है तो समय जटिलता ओ (एन^डी) है। ऐसा इसलिए है क्योंकि रिकर्सन गहराई प्रमुख कारकों की संख्या तक बढ़ जाएगी। लेकिन यह तंग बंधन नहीं है। कोई सुझाव?

Answer 1

2 विचार:

एल्गोरिथ्म उत्पादन के प्रति संवेदनशील है। एक गुणन Outputting सबसे हे (एन) पाश की पुनरावृत्तियों पर उपयोग करता मास्टर प्रमेय के माध्यम से ऐसा समग्र हम हे (एन * number_of_factorizations)

भी है,,, समीकरण है: F(N) = d * F(N/2) + O(N), इसलिए समग्र हम O(N^log_2(d))

Answer 2

है

समय जटिलता होना चाहिए:

number of iterations * number of sub calls^depth

हैं हे (लॉग एन) हे (एन) के बजाय उप कॉल, the number of divisors of N is O(log N)

टी के बाद से वह रिकर्सन की गहराई भी ओ (लॉग एन) है, और प्रत्येक रिकर्सिव कॉल के लिए पुनरावृत्तियों की संख्या एन/(2^गहराई) से कम है, इसलिए समग्र समय जटिलता ओ (एन ((लॉग एन)/2)^(लॉग एन))

Answer 3

The time complexity is calculated as : Total number of iterations multiplied 
by no of sub iterations^depth.So over all complexity id Y(n)=O(no of 
dividends)*O(number of factorization)+O(no of (factors-2) in loop); 

Example PrintFactors(12) 12 * 1 ,6 * 2, 4 * 3, 3 * 2 * 2 
O(no of dividends)=12 
O(number of factorization)=3 
O(no of factors-2){ in case of 3 * 2 * 2)=1 extra 

Over all: O(N^logbase2(dividends))