Помогите расшифровать этот код и его время выполнения

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

Так что я немного смущен тем, что делают массивы. Первая строка инициализирует 2D-массив с n столбцами. Первый для циклов смотрит на каждый столбец. Если это четный столбец, он поместит n в первую строку этого столбца. Теперь я немного смущен этим, потому что на него ссылаются только с одной скобкой, хотя это должен быть 2D-массив. То же самое с двойным циклом. В чем разница между A.length и A [i] .length? Из того, что я понимаю, двойные для циклов повторяются через массив и получают сумму всех элементов. Может кто-то прояснить это, потому что я немного потерял синтаксис.

Кроме того, мой инстинкт говорит, что этот код работает в O (n^2) раз, по крайней мере, из-за двойных циклов. Правильно ли это?

Answer 1

Это может помочь вам, если вы думаете об A не как 2D-массив (который мы обычно рассматриваем как прямоугольник), а как массив массивов из ints. Внешний массив содержит n массивов ints, каждый из которых может быть другого размера.

Что A[i] = new int [n] фактически делает это размещение массив размера п в i-ой элемент массива A. A[i].length длина массива хранится в положении я в А.

Ваши инстинкты о O (n^2), и вложенные для них петли в целом верны.

Answer 2

Похоже, что ваш алгоритм неполный.

В верхней части инициализирует 2D массив таким образом, что каждый элемент массива даже верхнего уровня имеет длину п и каждый нечетный элемент массива верхнего уровня имеет длину 1.

Во второй половине, внешние итерации цикла по всем элемент верхнего уровня. Существует n таких элементов. Для каждого из этих элементов внутренний цикл for суммирует подэлементы. Существуют чередующиеся n и 1 из этих элементов.

Если это Java, то по умолчанию содержимое каждого элемента массива int [] будет равно 0. Если это правда, то окончательная сумма будет равна 0. И вы потратите O (n * (n/2) + n)) = O (n^2), чтобы получить ответ.