Was wäre die Ausführungszeit für den folgenden Algorithmus?

Question

Der folgende Code gibt alle Primfaktoren der angegebenen Zahl n zurück.

Ansatz hinter dem Algorithmus:

Iterate über die Zahlen (d> = 2) bis n/i die Primfaktoren zu bekommen.

Die interne Schleife reduziert einfach die Größe der Zahl, indem sie durch die aktuelle Primzahl dividiert wird und wenn die gleiche Primzahl mehr als einmal erscheint, wird sie weiter geteilt.

Die if-Anweisung würde die letzte & die höchste Primzahl für n> 2 hinzufügen, da n zu diesem Zeitpunkt auf diesen Wert reduziert worden wäre.

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

Wie wird die Laufzeit für diesen Algorithmus bestimmt? Da jedes Mal, wenn die innere Schleife iteriert wird, verringert sie die Größe mit einem konstanten Wert, beispielsweise n/2, n/3, usw. basierend auf dem Index i, wenn es eine Primzahl ist.

Answer 1

Wenn Sie einen Algorithmus wie diesen analysieren, ist es oft hilfreich zu klären, ob Sie nach einer Best-Case-, Average-Case- oder Worst-Case-Analyse suchen, da die Antwort in jedem Fall unterschiedlich sein kann.

Beginnen wir mit einer Worst-Case-Analyse. Was müsste passieren, damit dieser Algorithmus so lange wie möglich läuft? Nun, wenn wir niemals Primfaktoren austeilen, wird die äußere Schleife so oft wie möglich laufen. Genauer gesagt wird es Θ (√ n) mal laufen. Dies ist nur der Fall, wenn es sich bei der betreffenden Zahl um eine Primzahl handelt. Daher können wir sagen, dass der Worst-Case-Fall bei Primzahl-Eingaben auftritt, bei denen die Laufzeit Θ (√ n) ist.

Was ist mit dem besten Fall? Nun, dieser Algorithmus wird entweder enden, wenn ich zu groß für n werde oder n zu klein für i wird. Es ist wesentlich schneller, n zu fallen, als i zu erhöhen, weil n geometrisch fällt, während ich arithmetisch zunimmt. Ein idealer Fall wäre eine Eingabe, die so schnell wie möglich abfällt, was passiert, wenn Sie eine Eingabe bereitstellen, die nur winzige kleine Faktoren enthält (diese heißen glatte Zahlen). Im Idealfall erhalten Sie eine perfekte Zweierpotenz, und in diesem Fall schneidet der Algorithmus n in der Hälfte wiederholt, bis er auf 1 fällt. Das ist das Kennzeichen des logarithmischen Verhaltens, so dass die Laufzeit im besten Fall Θ (log n).