-3

これは単純な選択ソートのコードです。通常、ソートの複雑さ（時間）は、選択ソートの場合にO（n ^ 2）をソートするために必要な反復回数です。このコードを98765のサンプル文字列に対してドライランしたとき、それは私に25回の反復を与えました。ドライラン出力とクロスチェックするために、コードに2つのvbl-noiとnojを入れました。

Q：合計反復回数は= noi*nojまたはnoi+nojになりますか。

int index = 0; int noi = 0, noj = 0;

for (j = 0; j < 5; j++)
{
    noj++;
    index = j;
    for (i = j; i < 5; i++)
    {
        if (a[index] > a[i])
        {
            a[index] = a[index] + a[i];
            a[i] = a[index] - a[i];
            a[index] = a[index] - a[i];
            noi++;
        }

    }

}
4

3 に答える 3

2

j<5ループにはとがあるため、反復回数は常に15（5 + 4 + 3 + 2 + 1）i<5です。したがって、コードの複雑度はO（n ^ 0）です。これは、この場合、nが5であるためです。

于 2012-12-10T11:50:00.420 に答える
2

がないため、複雑さはに依存しませnんn。複雑さは常に正確に15です（前述のshift66のように1 + 2 + 3 + 4 + 5）

于 2012-12-10T12:03:29.463 に答える
0

noj[最初のループの場合]+（（noj *（noj + 1））/ 2）[内部ループの場合]

最初のループは1-nojからのもので、2番目はj-nojです（jは最初のループに依存します）

于 2012-12-10T12:01:49.947 に答える