私はこの解決策をプログラミング練習サイトで見つけました。複雑さはO（N）です。しかし、それはO（N^2）のように見えます。なぜ誰かがO（N）なのか教えてもらえますか？この短いコードの実行時の複雑さはどのくらいですか？
public static void transposeMatrix(int[][] matrix) {
int n = matrix.length - 1;
int temp = 0;
for(int i = 0; i <= n; i++){
for(int j = i+1; j <= n; j++){
temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
}
Nとは何ですか？
Nがmax(matrix.length, matrix[0].length)の場合、アルゴリズムはO（N^2）です。
Nがであり、行列の合計サイズがである場合、アルゴリズムはO（N）です。
Nがbig-O表記のものを正確に定義することは常に重要です。 Big-Oを学ぶとき、ほとんどの議論は1次元の入力を中心に行われ、人々はあなたがNを定義する必要がないと仮定します。現実世界では、物事は汚れており、我々は多次元の入力を扱います。そして、あなたは何がNであるかを非常に明確にしなければなりません。
O（n）ではありません。それはO（n^2）です。具体的には、0≦i≦nのn-iスワップを実行します。したがって、0 + 1 + 2 + ... + n swaps = n（n + 1）/ 2 swapsを実行します。これはO（n^2）です。
n = matrix.length - 1;
時間計算：O（N^2）
スペース複雑：Oは、（1）
説明：ループの最初に、私は（0から行きます - - N）。そして、 の2番目のループでは、jは（i + 1 --- N）になります。 i = 0の場合、 N-1要素を反復します。 i = 1の場合、N-2個の要素を反復します。同様に、I = N-1のために、あなたはあなたが正しい
In total, T = (N-1) + (N-2) + (N-3) + ... + 2 + 1
T ~ N * (1+2+3+...+N)
T ~ O(N^2)
最後の要素のために反復します。その情報源は間違っています。 –
Nの別の定義を使用している可能性があります。 – user2357112
ソースとは何ですか？ –