1

私は非常に単純なアルゴリズム分析を解決しようとしています（明らかに私にはそれほど単純ではありません）。

アルゴリズムは次のようになります。

int findIndexOfN(int A[], int n) {
// this algorithm looks for the value n in array with size of n.
// returns the index of n in case found, otherwise returns -1.
// it is possible that n doesn't appear in the array.
// n appears at most one time.
// the probability that n doesn't appear in the array is $1/(n+1)$
// for each cell in the array, the probability that n is found in index i
// is $1/(n+1)$


    int index, fIndex;
    index = 0;
    fIndex = -1;
    while (index < n && fIndex == -1) {
      if(A[index] == n) {
        fIndex = index;
      }
      index++;
    }
    return fIndex;

 }

今、私は平均実行時間を計算しようとしています。これは等比数列だと思いますが、確率と複雑さという用語をマージする方法を見つけることができません。

たとえば、値nがインデックス1で見つかった場合、2番目のインデックス（1）を取得してnを見つけるには、1ループステップかかることがわかっています。

一方、確率は私にいくつかの分数を与えます....

これが私がこれまでに得たものです：

i=1からnまでの$\sigma評価（（1 / n）*（（n-1）/ n）^ i-1）

しかし、繰り返しになりますが、この式とT（n）の関係を見つけることができず、この関数のBigOh、BigOmega、またはThetaの関係も見つけることができません。

4

1 に答える 1

1

このアルゴリズムは、BigOh(n)、BigOmega(n)、および Theta(n) です。

これを知るために、確率を計算したり、マスター定理を使用したりする必要はありません (関数は再帰的ではないため)。関数が項のループのようなものであることを確認する必要がありますn。関数を次のように表現した方が簡単かもしれません。

for (int i = 0; i < n; ++i) {
    if (A[i] == n)
        return i;
}

nifが配列の最初の要素である場合、実際にはそれを見つけるために必要な操作は 1 つだけなので、これは直感に反しているように思えます。ここで重要なのは、が配列の真ん中にある一般的なケースです。n

このように言いましょう: あなたが書いた確率を考えるとn、要素n/4と3n/4配列の間に 50% の確率があります。この場合、 と の間n/4の3n/4テストで要素を見つける必要があり、これは に評価されO(n)ます (BogOh 分析を行うときに定数を削除します)。

必要な操作の平均数を知りたい場合は、質問に書いたようにシリーズを計算できます。操作の平均数を与える実際のシリーズは

1/(n+1) + 2/(n+1) + 3/(n+1) ... + n/(n+1)

なんで？nが最初の位置にある場合は 1 つのテスト(確率1/(n+1))、2n番目の位置にある場合は 2 つのテスト (確率1/(n+1))、 ...が 2 番目の位置にあるi場合nはテスト (確率)が必要なためです。i1/(n+1)

このシリーズは次のように評価されます

n(n+1)/2 * 1/(n+1) = n/2
于 2012-11-02T19:01:29.913 に答える