Hilfe entziffern diesen Code und es ist Laufzeit

Question

int[][] A = new int [n][]; 
for (int i=0; i<n; i++) { 
    if (i % 2 == 0) // i is a multiple of 2 
     A[i] = new int [n]; 
    else 
     A[i] = new int [1]; 
} 

for (int i=0; i<A.length; i++) 
    for (int j=0; j<A[i].length; j++) 
     sum = sum + A[i][j]; 

So bin ich ein bisschen verwirrt darüber, was die Arrays tun. Die erste Zeile initialisiert ein 2D-Array mit n Spalten. Die erste for-Schleife betrachtet jede Spalte. Wenn es eine gerade Spalte ist, wird n in die erste Zeile dieser Spalte geschrieben. Jetzt bin ich ein bisschen verwirrt, weil es mit nur einer Klammer referenziert wird, obwohl es ein 2D-Array sein sollte. Das gleiche gilt für die doppelten for-Schleifen. Was ist der Unterschied zwischen A.length und A [i] .length? Soweit ich weiß, durchlaufen die doppelten for-Schleifen das Array und erhalten die Summe aller Elemente. Kann jemand das klären, weil ich ein bisschen in der Syntax verloren bin.

Auch mein Instinkt sagt, dass dieser Code zumindest wegen der doppelten for-Schleifen in O (n^2) -Zeit läuft. Scheint das richtig?

Answer 1

Es kann Ihnen helfen, wenn Sie an A nicht als ein 2D-Array denken (das wir normalerweise als rechteckig denken), sondern als ein Array von Arrays von Ints. Das äußere Array enthält n Arrays von Ints, von denen jedes eine andere Größe haben kann.

A[i] = new int [n] Was tatsächlich tut, ist eine Matrix der Größe n in der i-ten Element des Feldes A. Anordnen A[i].length ist die Länge der Anordnung in der Position gespeichert i in A.

Ihre Instinkte über O (n^2) und die verschachtelten for loops sind hier generell korrekt.

Answer 2

Offenbar ist Ihr Algorithmus unvollständig.

Der obere Teil initialisiert eine 2D-Array, so dass jedes gerade Top-Level-Datenfeldelement Länge n hat und jedes ungeradees oberste Ebene Feldelement hat die Länge 1.en

In der zweiten Hälfte der äußeren Schleife iteriert über all das oberste Element. Es gibt n solche Elemente. Für jedes dieser Elemente summiert die innere for-Schleife die Unterelemente. Es gibt abwechselnd n und 1 dieser Elemente.

Wenn dies Java ist, dann wird standardmäßig der Inhalt jedes int [] -Arrayelements 0 sein. Wenn das wahr ist, dann ist die endgültige Summe 0. Und Sie haben O (n * (n/2) ausgegeben + n)) = O (n^2), um diese Antwort zu erhalten.