現在のインデックスに関連するサイズの配列の実行時の複雑さを計算するにはどうすればよいですか？

Question

私は以下の関数の実行時の複雑さを理解しようとしています。与えられた数の素因数を求める。

function test(n){ 
    n = parseInt(n); 

    var factors = []; 

    for(var i = 2; i <= n; i++){ 
     while((n % i) === 0){ 
      factors.push(i); 
      n /= i; 
     } 
    } 

    return factors; 
} 

whileループの実行は、iの値に依存し、私はそれを計算またはIこれはO（N2）、右ではないはずできるか分かりませんか？

Answer 1

外側のforループがO(n)であることは明らかです。ここのトリッキーな部分は、内側のwhileループです。このループは、与えられた値nの素因数の数を計算しています。したがって、明示的な関数、または少なくとも上限を計算して素因数を計算すると、nを掛けて全体の境界を得ることができます。

私は、私たちの姉妹サイト、数学スタック所に次の二つの役に立つの質問が見つかりました：あなたのループのため

log(n)/log(log(n)) 

：彼らの両方が上限であることを明らかにし

https://math.stackexchange.com/questions/938204/upper-bound-number-of-distinct-prime-factors https://math.stackexchange.com/questions/1972003/upper-bound-for-count-of-unique-prime-divisors

を直接入れ子になっているので、2つの複雑さを掛け合わせるだけで、次のようになります。

O(n*log(n)/log(log(n)))