0

わかりました、私は Big O の概念を理解しようとしています。私は Big O を見つけると思われる関数を持っていますが、完全に「理解」していません。これは私の宿題のような本の例です..答えが O(nk) であることはわかっていますが、誰かがこれを単純化して説明してくれるので、理解を深めることができます。

int selectkth(int a[], int k, int n)
{
int i, j, mini, tmp;
for (i=0; i < k; i++)
{
mini = i;
for (j = i+1; j < n; j++)
{
if (a[j] < a[mini])
mini = k;
tmp = a[i];
a[i] = a[mini];
a[mini] = tmp;
}
}
return a[k-1];
}
4

1 に答える 1

1

bigO を計算するときは、最悪の時間計算量を考え、ループに注意してください。ここには 2 つのループがあります。

// 以下の行は k 回実行されます

for (i=0; i < k; i++)

// 最悪の場合、以下のループは n 回実行されます。

for (j = i+1; j < n; j++)

bigO は、これら 2 つの値を掛け合わせたもの = k*n になります。

この投稿もチェックしてください: "Big O" 表記の平易な英語の説明とは?

于 2013-04-10T00:47:47.717 に答える