0 
P(x,y,z){
    print x
    if(y!=x) print y
    if(z!=x && z!=y) print z
}

ここでの自明なアルゴリズムでは、値x、が からランダムに選択さyれます。このアルゴリズムの平均的なケースの複雑さを判断しようとしており、print ステートメントの数に基づいて複雑さを測定しています。z{1,...r}r >= 1

ここでの最良のケースは T(n) = 1 または O(1) でx=y=zあり、その確率は 1/3 です。ここでの最悪のケースは、確率が 2/3 の
場合でも T(n) = 3 または O(1)です。x!=y!=z

しかし、平均的なケースを数学的に導出する場合:
サンプル空間は n 可能な入力、サンプル空間に対する確率は 1/n の可能性です。（これは私が空白を描くところです..）

4

4 に答える 4

1

Your algorithm has three cases:

  1. All three numbers are equal. The probability of this is 1/r, since once you choose x, there's only one choice for y and for z. The cost for this case is 1.
  2. x != y, but x == z or y == z. The probability of this is 1/r * (1/(r - 1))* 1/2, since once you choose x, you only have r -1 choices left for y, and z can only be one of these two choices. Cost = 2.
  3. All three numbers are distinct. Probability that all three are distinct is 1/r * (1/(r - 1))*(1/(r - 2)). Cost = 3.

Thus, the average case can be computed as:

1/r  + 1/r * (1/(r - 1)) + 1/r * (1/(r - 1))*(1/(r - 2)) * 3 == O(1)

Edit: The above expression is O(1), since the whole expression is made up of constants.

于 2012-05-21T12:48:18.710 に答える
0

1) 少なくとも一般的なケースをプログラムできますか? (疑似) コードを書き、それを分析すると、すぐに明らかになるかもしれません。実際には最適ではないプログラムを作成する可能性があり、より良い解決策が存在する可能性があります。これは非常に典型的なことであり、コンピュータ サイエンスの数学の端にある謎解きの一部です。たとえば、並べ替えをコーディングしようとしているだけでは、自分でクイック並べ替えを見つけるのは困難です。

2) 可能であれば、モンテカルロ シミュレーションを実行し、結果をグラフ化します。つまり、N = 1、5、10、20、...、100、1000、または現実的なサンプルであれば、10000 回試行して平均時間をプロットします。運が良ければ、X = サンプル サイズ、Y = 平均です。そのサンプル サイズで 10000 回の実行にかかる時間は、きれいな線、放物線、またはモデル化しやすい曲線をグラフ化します。

したがって、（1）アルゴリズムの検索またはコーディング、または（2）分析の助けが必要かどうかはわかりません。おそらく、これを指定するために質問を修正することをお勧めします。

于 2012-05-21T00:50:32.770 に答える
0

平均的なケースは、最良のケースと最悪のケースの間のどこかになります。この特定の問題については、これで十分です (少なくとも Big-O までは)。

于 2012-05-20T23:36:27.803 に答える