このコードとランタイムを解読するのに役立ちます

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列の2D配列を初期化します。最初のforループは各列を調べます。それが偶数列の場合は、その列の最初の行にnを入れます。今はちょっと混乱していますが、それは2D配列でなければならないにもかかわらず1つの括弧で参照されているからです。ループのための二重と同じもの。 A.lengthとA [i] .lengthの違いは何ですか？私が理解していることから、ループの二重ループは配列全体を反復し、すべての要素の合計を取得しています。誰かがこれを明確にすることはできますか？なぜなら私は文法について少し失われているからです。

また、私の本能は、このコードは少なくとも2回のループのためにO（n^2）時間で実行されると言います。それは正しいようですか？

Answer 1

2次元配列ではなく（私たちは一般的に矩形であると考えていますが）、intの配列の配列として考えることができます。外側の配列には、intのn個の配列が含まれています。それぞれの配列のサイズは異なる場合があります。 A[i] = new int [n]が実際に配列A A[i].lengthのi番目の要素で、サイズnの配列を配置しているやっている何

は、（配列の長さはA.に位置i Oについて

あなたの本能を格納していますn^2）とネストされたforループは、ここでは一般的に正しいです。

Answer 2

あなたのアルゴリズムは不完全であるようです。

上部はすべても、トップレベルの配列要素は、長さnとを有するように、2次元アレイを初期化し、すべての奇数のトップレベルの配列要素は、長さを超えるすべての後半において

、外側のループ反復を有します最上位の要素そのような要素はn個あります。これらの要素のそれぞれについて、内側のforループがサブ要素を合計します。 nと1の要素が交互に存在します。

これはJavaの場合、デフォルトですべてのint []配列要素の内容は0になります。これが真であれば、最終的な合計は0になります。そして、O（n *（n/2） + n））= O（n^2）と答えます。