Aidez à déchiffrer ce code et son exécution

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

Donc, je suis un peu confus sur ce que les baies font. La première ligne initialise un tableau 2D avec n colonnes. La première pour les boucles regarde chaque colonne. Si c'est une colonne paire, elle mettra n dans la première ligne de cette colonne. Maintenant, je suis un peu confus à ce sujet, car il est référencé avec un seul support, même si ce devrait être un tableau 2D. La même chose avec le double pour les boucles. Quelle est la différence entre A.length et A [i] .length? D'après ce que je comprends, le double pour les boucles est itérer à travers le tableau et obtenir la somme de tous les éléments. Quelqu'un peut-il clarifier cela parce que je suis un peu perdu sur la syntaxe. Mon instinct dit aussi que ce code s'exécute en O (n^2) à tout le moins à cause du double pour les boucles. Est-ce que cela semble juste?

Answer 1

Cela peut vous aider si vous considérez A non comme un tableau 2D (que nous considérons généralement comme rectangulaire) mais comme un tableau de tableaux d'entiers. Le tableau externe contient n tableaux d'entiers, dont chacun peut avoir une taille différente.

Qu'est-ce que A[i] = new int [n] est en train de faire est de placer un tableau de taille n dans l'élément i'th du tableau A. A[i].length est la longueur du tableau stocké à la position i dans A.

Vos instincts sur O (n^2) et les boucles imbriquées sont généralement correctes ici.

Answer 2

Votre algorithme semble incomplet.

La partie supérieure initialise un tableau 2D de telle sorte que chaque même élément de réseau de niveau supérieur a une longueur n et chaque élément de réseau de niveau supérieur impair est de longueur 1.

Dans la seconde moitié, les itérés de boucle externe sur toute l'élément de niveau supérieur. Il y a n éléments de ce type. Pour chacun de ces éléments, la boucle interne interne additionne les sous-éléments. Il y a alternance n et 1 de ces éléments. Si c'est Java, alors par défaut le contenu de chaque élément int [] sera 0. Si c'est vrai, alors la somme finale sera 0. Et vous aurez dépensé O (n * (n/2) + n)) = O (n^2) pour obtenir cette réponse.