2

私は自分のアルゴリズムで数学を正しくしようとしていますが、ieなどを計算する「アルゴリズムの分析」を理解するのに非常に苦労していf(n) = 1ますf(n) = n-1。

ソートされた整数の配列をループし、異なる整数がいくつあるかを数えるメソッドを作成しました（つまり{1,3,3,3,5,6,8} = 5）。最悪のシナリオを計算するにはどうすればよいですか？

基本的に、コードは次のようになります。

int length = a.length;
int diffCount = 1; //The number of different integers

for(int i = 1; i < length; i++)
{
    int b = a[i];
    int c = a[i-1];

    if(c>b)
         throw new IllegalStateException("unsorted array");

    if(c!=b)
         diffCount++;
}
return diffCount;

他にもいくつかありますが、それは空の配列などのバグを防ぐためだけなので、含めませんでした。

そして、ここでの最悪のシナリオは何ですか..？条件c!=bが毎回真である場合は？

4

3 に答える 3

4

ランタイム分析に関しては、配列がソートされている場合、このアルゴリズムは常にO(n)です。そうでない場合は、その前に例外がスローされます (ただし、最悪の場合はO(n)です)。

値によって結果が若干異なります。分岐予測の説明については、Peter の回答を参照してください。しかし、これが実行時間に大きな影響を与えるとは思いません。

于 2012-09-13T14:30:38.163 に答える
1

理論的には、このループの実行にかかる時間は、特定の長さの配列に対して常に同じになります。

分岐予測が影響を受ける可能性があるかどうかを調べましたが、この場合、JIT が 2 番目の分岐を排除するのに十分スマートであるため、そうではないようです。

Cでは、ブランチを次のように削除できます

diffCount += c != b;

おそらくJITは同様のことをします。

于 2012-09-13T14:21:59.823 に答える
1

一般に、複雑さを分析するときは、アルゴリズムで最も遅い操作と思われるものに注目します。ソートアルゴリズムについては、比較を選択すると思います。あなたのコードでは、2 つの配列アクセスを選択します。

int b = a[i];
int c = a[i-1];

または2つの比較さえ：

if (c != b) …

の代わりにdiffCount++。これは、比較の結果が常に発生するため、重要ではないことを意味します。

もちろん、複数の操作の観点から複雑さを分析することもできます。たとえば、並べ替えについては、要素の交換だけでなく、要素の比較も確認できます。または、あなたの場合diffCount++、メモリ書き込みが比較よりもはるかに遅いと予想されるため、集中したい場合があります。

私が選択した操作はヒットa.length時間を取得するため、それがアルゴリズムの複雑さです。

この選択された操作が条件の下にある場合、(Big-O の複雑さを探すときに)条件がヒットする頻度の妥当な上限を選択する必要があります。したがって、あなたの場合、c != bチェックされたすべての要素のペアに対して真である入力配列が可能であれば、分析では常に真であると想定できます。

于 2012-09-13T14:35:49.713 に答える