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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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