0

こんにちは私はそれらの複雑さを解決する必要がある2つのアルゴリズムを持っています、私は最初に自分自身を試しました。O（N ^ 2）＆O（N ^ 3）ここにあります：

Yを「y=int [N] [N]」と宣言されているかのように扱い、Bを「B = int[N][N]」と宣言されているように扱います。

int x(int [] [] y)
{
int z = 0
for (int i =0; i<y.length; i++)
    z = z + y[i].length;
  return z;
}

int A (int [] [] B)
{
    int c =0
    for ( int i =0; i<B.length; i++)
        for (int j =0; j<B[i].length; j++)
             C = C + B[i] [j];
    return C;
}

どうもありがとう ：）

4

1 に答える 1

1

アルゴリズムの複雑さを計算するには、アルゴリズムで実行された操作の数を集計する必要があります (big-O 表記は最悪のシナリオを懸念しています)。

最初のケースでは、N 回 (y.length==N) 実行されるループがあります。ループ内には 1 つの操作があります (反復ごとに実行されます)。これは入力数に比例するため、O(x)=N です。

注: y[i].length の計算は、一定の長さの操作です。

2 番目のケースでは、(最初のケースと同様に) N 回実行される外側のループがあり、同じ長さ (N==B[i].length) の場合、各反復で別のループが実行されます。内側のループ内には、1 つの操作があります (内側のループの反復ごとに実行されます)。これは全体で O(N*N)==O(N^2) です。

注：b [i] [j]の計算は一定の長さの操作です

注: big-O の場合、最も急速に成長する項のみが重要であるため、追加の定数は無視できることに注意してください (たとえば、戻り値の初期化と戻り命令はどちらも操作ですが、定数であり、ループで実行されません。 N に依存する項は、定数よりも速く成長します)

于 2012-06-07T11:42:31.997 に答える