Ich glaube, dieser Algorithmus ist O (N). Hab ich recht?

Question

Dieser Algorithmus kehrt ein Array von N ganzen Zahlen um. Ich glaube, dass dieser Algorithmus O (N) ist, weil für jede Schleifeniteration die vier Codezeilen einmal ausgeführt werden, wodurch der Job in 4N Zeit abgeschlossen wird.

public static void reverseTheNumbers(int[] list) { 
    for (int i = 0; i < list.length/2; i++) { 
     int j = list.length - 1 - i; 
     int temp = list[i]; 
     list[i] = list[j]; 
     list[j] = temp; 
    } 
} 

Answer 1

Es gibt nicht so etwas wie 4N Zeit. Der Algorithmus ist linear, da die Laufzeit des Algorithmus proportional zunimmt, wenn Sie die Größe der Eingabe erhöhen. Mit anderen Worten, wenn Sie die Größe von list verdoppelt haben, würden Sie erwarten, dass der Algorithmus doppelt so lange dauert.

Es spielt keine Rolle, wie viele Operationen Sie innerhalb Ihrer Schleife ausführen - solange sie jede konstante Zeit (relativ zur Eingabe) sind, wird die Laufzeit der Schleife einfach durch die Anzahl der Iterationen bestimmt.

Mit anderen Worten, diese vier Aussagen sind - alle zusammen - eine O (1) -Operation.

int j = list.length - 1 - i; 
int temp = list[i]; 
list[i] = list[j]; 
list[j] = temp; 

Es gibt nichts signifikant über die Tatsache, dass diese Abfolge von Schritten in vier Aussagen in Java-Syntax ausgedrückt wird - mit javap experimentieren diese vier Linien Befehle kompiliert in ~ 20 Bytecode schon sagt, und wer weiß, wie viele Prozessorbefehle, die Bytecode wird in konvertiert. Die gute Nachricht ist, dass die Big-O-Notation unabhängig von der jeweiligen Syntax gleich funktioniert - eine Folge von Operationen ist O (1) oder konstante Zeit, wenn ihre Ausführungszeit unabhängig von der Eingabe gleich ist.

Daher machen Sie eine O (1) Operation N-mal; alias O (N).

Answer 2

Ja, Sie haben Recht. Die Anzahl der Operationen ist linear abhängig von der Größe des Arrays (N), was es zu einem O (N) -Algorithmus macht.

Answer 3

Ja, die Komplexität des Algorithmus ist O (n). Allerdings ist die genaue "Zeit" (weil es keine konstanten Faktoren in asymptotischer Komplexität gibt, siehe Kommentar unten) nicht 4 mal so groß wie das Array, wir könnten sagen, es ist 1/2 * (c1 + c2 + c3 + c3) mal die Größe des Arrays, wobei 1/2 jeder Schleifeniteration entspricht und jedes c der Zeit entspricht, die für jede Operation innerhalb der Schleife benötigt wird. Es wäre 4-mal so groß wie das Array, wenn der Algorithmus das ganze Array 4-mal durchlaufen würde.