3

X行Y列の行列があるとしましょう。要素の総数はX*Yですよね？それで、n = X * Yになりますか？

for (i=0; i<X; i++)
{
   for (j=0; j<Y; j++)
   {
      print(matrix[i][j]);
   }
}

では、このネストされたforループがO（n）であることを意味するのではないでしょうか。それとも、時間計算量がどのように機能するかを誤解していますか？

一般に、ネストされたforループはすべてO（n ^ 2）だと思いましたが、print（）へのX * Y呼び出しを通過する場合、時間計算量がO（X * Y）とX*Yであることを意味するわけではありません。 nに等しい？

4

4 に答える 4

1

サイズの行*列の行列がある場合、内側のループ（たとえば）はO（列）であり、ネストされたループは一緒にO（行*列）です。

問題サイズNと問題サイズN^2を混同しています。行列のサイズがNであるか、行列のサイズがN ^ 2であると言うことができますが、行列が正方形でない限り、行*列のサイズの行列があると言う必要があります。

于 2012-04-27T04:48:36.270 に答える
1

あなたが言うときは正しいですがn = X x Y、ネストされたループはであるはずだと言うときは間違っていますO(n)。コードをドライランすると、ネストされたループの意味を理解できます。外側のループが繰り返されるたびに、内側のループがn（またはサイズ条件が何であれ）実行されることに気付くでしょう。したがって、簡単な計算で、そのことを推測できますO(n^2)。ただし、反復するときにループが1つしかない場合(X x Y)（例：for(i = 0; i<(X*Y); i++)要素の場合、O(n)どの時点でも反復を再開しないことが原因になります。これが理にかなっていることを願っています。

于 2012-04-27T04:49:09.190 に答える
0

一般的に、ネストされたforループはすべてO（n ^ 2）だと思いました。

あなたはそれについて間違っています。混乱するのは、正方形（X == Y）行列の例としてよく使用されるため、複雑さはn * n（X == n、Y == n）であるということです。

O（*）スキルを練習したい場合は、行列の乗算がO（n ^ 3）である理由を理解してください。行列乗算のアルゴリズムがわからない場合は、オンラインで簡単に見つけることができます。

于 2012-04-27T04:54:11.463 に答える
0

この回答は急いで書かれ、いくつかの反対票を受け取ったので、私はそれを明確にして書き直すことにしました

アルゴリズムの時間計算量は、アルゴリズムが解決しようとしている問題のサイズに関するアルゴリズムの操作数の表現です。

ここには2つのサイズがあります。

  1. 最初のサイズは、行列X×Yの要素の数です。これは、複雑さの理論で入力のサイズとして知られているものに対応します。k=X×Yが行列内の要素の数を表すとします。ツインループの演算数はX×Yなので、O（k）になります。

  2. 2番目のサイズは、行列の列と行の数です。m = max（X、Y）とします。ツインループの演算数はO（m ^ 2）です。通常、線形代数では、この種のサイズは、m×m行列での行列演算の複雑さを特徴づけるために使用されます。

複雑さについて話すときは、インスタンスの問題をエンコードする方法と、そのサイズを指定するために使用するパラメーターを正確に指定する必要があります。複雑性理論では、通常、アルゴリズムへの入力は有限のアルファベットからの文字列として与えられると想定し、アルゴリズムの複雑さを、によって与えられる問題のインスタンスに対する操作数の上限の観点から測定します。長さnの文字列。これは複雑性理論にあります。nは通常入力のサイズです。

アルゴリズムの実際の複雑さの分析では、特定のコンテキストでより意味のあるインスタンスのサイズの他の測定値を使用することがよくあります。たとえばA、がグラフの接続性行列であるV場合、問題のインスタンスの複雑さの尺度として頂点の数を使用できます。または、Aがベクトル空間に作用する線形演算子の行列である場合、次元を使用できます。そのような尺度としてのベクトル空間の。正方形の場合行列の慣例では、行列の次元の観点から複雑さを指定します。つまり、nの観点からn×n行列に作用するアルゴリズムの複雑さを測定します。それはしばしば実用的に意味があり、複雑性理論の慣習と矛盾する場合でも、特定のアプリケーション分野の慣習に同意します。

ツインループにMatrixScanという名前を付けましょう。Matrix Scanのインスタンスのサイズが、マトリックスの文字列エンコーディングの長さである場合、合法的に言うことができます。エントリの制限されたサイズを想定すると、それは行列内の要素の数kです。次に、マトリックススキャンの複雑さはO（k）にあると言えます。一方、インスタンスの複雑さを特徴付けるパラメーターとしてm = max（X、Y）を使用する場合、多くのアプリケーションで一般的であるように、X×Yマトリックスの複雑さのマトリックススキャンもO（ m ^ 2）。正方行列の場合、X = Y = mおよびO（k）= O（m ^ 2）。

注意：コメントの一部の人々は、多項式問題を線形問題に減らすために、問題の符号化を常に見つけることができるかどうかを尋ねました。本当じゃない。一部のアルゴリズムでは、操作の数は、入力の文字列エンコーディングの長さよりも速く増加します。たとえば、2つのm×m行列にθ（m ^ 2）個の演算を乗算するアルゴリズムはありません。ここでは、入力のサイズはm ^ 2として増加しますが、Ran Razは、操作の数が少なくともm ^ 2logmと同じ速さで増加することを証明しました。nがO（m ^ 2）にある場合、m ^ 2 log mはO（n log n）にあり、最もよく知られているアルゴリズムの複雑さは、O（m ^（2 + c））= O（n ^（1+ c / 2））、ここで、cはCoppersmith-Winogradアルゴリズムのバージョンでは少なくとも0.372であり、一般的な反復アルゴリズムではc=1です。

于 2012-04-27T04:56:44.083 に答える