次のアルゴリズムの実行時間はどのくらいですか？

Question

次のコードは、指定された数nのすべての素因数を返します。アルゴリズムの背後にある

アプローチ：数字上

反復（すなわち、> = 2）NまでI /素因数を取得します。

内部ループは、単純に現在の素数で割ることによって数値のサイズを減らし、同じ素数が複数回現れた場合、分割を継続します。

ifステートメントは、最後の&をn> 2の最も高い素数に加算します。これは、nがその時間までにその値に縮小されているためです。

static List<Integer> getAllPrimes(int n){ 
      List<Integer> factors = new ArrayList<Integer>(); 
      for(int i = 2 ; i <= n/i ; ++i){ 
       while(n % i == 0){ 
        factors.add(i); //LINE 1 
        n/=i; 
       } 
      } 
      if(n > 2){factors.add(n);} 
      return factors; 
} 

このアルゴリズムの実行時間はどのように決定されますか？以来、内側のループが反復されるたびに、素数ならインデックスiに基づいていくつかの一定値、例えばn/2、n/3 ....などでサイズが減少します。

Answer 1

このようなアルゴリズムを分析すると、それぞれのケースで回答が異なる可能性があるため、ベストケース、平均ケース、または最悪ケースの分析を探しているかどうかを明確にすると役立ちます。

最悪の場合の分析から始めましょう。このアルゴリズムをできるだけ長く実行するにはどうすればよいでしょうか？まあ、素因数を決して分けなければ、外側のループはできるだけ多くの回数実行されます。具体的には、Θ（√ n）回実行されます。これは問題の数値が素数である場合にのみ発生し、最悪の場合は素数入力で発生し、実行時間はΘ（√ n）となります。

最高のケースはどうですか？このアルゴリズムは、nが大きすぎるとnが小さすぎるか、または小さすぎるかのいずれかで終了することになります。 nが幾何級数的に下がるので、iを増やすよりもnを落とす方がはるかに高速です。理想的なケースは可能な限り速く落ちる入力です。小さな小さな要素（滑らかな数字と呼ばれます）しか持たない入力を入力すると起こります。理想的なケースでは、完全な2のべき乗を得ます。その場合、アルゴリズムはnが半分になるまで繰り返しnを1に減らします。これは対数的な振る舞いの特徴です。したがって、最良の場合、ランタイムはΘ n）。