5

重複の可能性
：for iの複雑さは何ですか：for o = i + 1

長さ5の配列に対して次の並べ替えアルゴリズムを実行しました。

int myarray[5] = {2,4,3,5,1};
    int i;
    for (i = 0; i < 5; i++)
    {
        printf("%d", myarray[i]);

        int j;
        for (j=i+1; j < 5; j++) 
        {
            int tmp = myarray[i];
            if (myarray[i] > myarray[j]) {
                tmp = myarray[i];
                myarray[i] = myarray[j];
                myarray[j] = tmp;
            }
        }
    }

この並べ替えアルゴリズムの複雑さは、O(n*n)要素ごとに他の要素と比較するためだと思います。ただし、外側のループで作成するたびに、残りのすべてと比較するのではなく、残りの部分と比較することにも気付きます-i。複雑さは何でしょうか？

4

8 に答える 8

7

それはまだですO(n²)（またはO(n * n)、あなたが書いたように）。計算の複雑さを分析する場合、重要なのは最上位の項のみです。

于 2013-01-23T16:34:25.580 に答える
5

あなたは正しいです：
それはO（1 + 2 + 3 ... + N）です
が、数学的には：
= O（n *（（n-1）/ 2））
ですが、それはただ：
= O（n ^ 2）

于 2013-01-23T16:36:06.793 に答える
3

あなたは正しいです、それはO（n 2）です。

計算方法は次のとおりです。最初の反復では、n個の要素を確認します。次に、n -1など。その合計の2つのコピーを作成し、2で割ると、最初のコピーnの最初の項を2番目のコピー1の最後の項に追加するように、項をペアにすることができます。n + 1のコピーがn個あるため、合計はn *（n + 1）/2になります。Big -Oは漸近的な動作のみを区別します。漸近的振る舞いは、定数係数n 2に関係なく、最高次の項で記述されます。

n +（n -1）+（n -2）... + 1
  = 2 *（n +（n -1）+（n -2）... + 1）/ 2
  =（（n + 1） +（n --1 + 2）+（n --2 + 3）+ ... +（1 + n））/ 2
  =（（n + 1）+（n + 1）+ ... +（n + 1））/ 2
  = n *（n + 1）/ 2
  = 1/2 * n 2 + 1/2 * n
  = O（n 2）

于 2013-01-23T16:46:04.450 に答える
2

これはバブルソートであり、実際には複雑ですO（n ^ 2）

アルゴリズムの実行時間全体は、次の合計で推測できます。

n +（n-1）+（n-2）+ ... + 1 = n（n + 1）/ 2

漸近解析では最上位の項のみが対象となるため、複雑さはO（n ^ 2）です。

于 2013-01-23T16:34:11.510 に答える
2

大きなO表記は漸近線です。これは、などの一定の要因を見落としていることを意味し- iます。アルゴリズムの複雑さは次のとおりですO(N²)（ここも参照）。

于 2013-01-23T16:34:17.623 に答える
1

複雑さはO(1)です。このO表記は、大きな入力に対してのみ意味があります。ここで、増加または減少が表示されるだけでなく、関連性があります。

あなたがそれを拡張するならば、それはO(n^2)そうでしょう。

于 2013-01-23T16:35:25.487 に答える
1

複数のループの場合

n * m*..ループ数

上記のコードの場合、最悪の場合、そのn * n = n ^ 2

BigOhは最大限界を意味します。

したがって、最大の複雑さはこれより大きくなることはできません。

于 2013-01-23T16:36:26.003 に答える
0

i = 0の場合、n時間実行されます

i=1それはn-1回実行されます

i=2それはn-2時間実行されます...。

  So total Sum = (n) + (n-1) + (n-2) + .... + 1
           sum =  (n*n) - (1 + 2 + ...)
               =  n^2   -

非常に大きなOの複雑さ=O（n ^ 2）{上限; +または-は無視されます}

于 2013-01-23T17:08:10.540 に答える