このアルゴリズムの時間の複雑さは何ですか

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); 
     } 
    } 
} 

私は、それが

所定数はN及びN = Dの素因数の数である場合

だと思います時間複雑度はO（N^d）である。これは、再帰の深さが素因数の数に達するためです。しかし、縛られていない。助言がありますか？

Answer 1

2つのアイデア：

アルゴリズムは出力に影響されます。因数分解を出力するので、全体的に、我々はO（N * number_of_factorizations）が、ループのほとんどO（N）回の反復で、最大使用

また、マスターの定理を経由して、式は次のとおりです。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)

Tので、O（Nログ）の代わりにO（N）のサブコール、再帰呼び出しの深さはO（log N）であり、すべての再帰呼び出しの反復回数はN /（2 ^深さ）よりも小さいため、全体の時間複雑度はO（N（（log N）/ 2） N））

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))