1

100ページの絵本があります。ページの 1 つを選択するためにサイコロをランダムに振った後、本の特定の写真を検索するためにサイコロを振り直した場合、この問題の最高、最悪、平均のケースの複雑さをどのように判断すればよいでしょうか?

提案された答え:

最良のケース: 画像は最初のサイコロの目で見つかります

最悪のケース: 100 番目のダイスのロールで画像が見つかるか、画像が存在しない

平均的なケース: サイコロを 50 回振った後に画像が見つかる (= 100 / 2)

仮定: 正しくない画像は最大 1 回検索されます

4

4 に答える 4

6

問題についてのあなたの説明を考えると、あなたの仮定（間違った写真は一度だけ「検索」される）は正しく聞こえないと思います。その仮定をしないと、答えは以下のようになります。答えはあなたが提案したものとは多少異なることがわかります。

  1. 最初の試みで成功する可能性があります。したがって、最初の答えは1です。
  2. 運が悪ければ、間違った番号を永遠に転がし続ける可能性があります。したがって、2番目の答えは無限大です。
  3. 3番目の質問はあまり明白ではありません。

ロールの平均数はいくつですか？あなたは幾何分布に精通している必要があります：単一の成功を得るために必要な試行の数。

  • 試行が成功する確率としてpを定義します。p =0.01。
  • Pr（x = k）を、最初に成功した試行がk番目である確率とします。次に、（k -1）の失敗と1つの成功が必要になります。したがって、Pr（x = k）=（1- p）^（k -1）*p。これがwikiページ（左の列）の「確率質量関数」であることを確認します。
  • 幾何分布の平均は1/ pであるため、100になります。これは、特定の画像を見つけるために必要なロールの平均数です。

（注：0ではなく1を可能な限り低い値と見なす必要があるため、Wikipediaページの表の左側の列を使用してください。）

于 2010-01-23T09:42:09.193 に答える
2

最悪のケースは、100個のサイコロを振った後に見つかったページではありません。つまり、サイコロは常に異なる数字を返します。最悪の場合は、ページが見つからないことです（問題を述べた方法）。

幸いなことに、平均的なケースは最良のケースと最悪のケースの平均ではありません。

平均的なケースは次のとおりです。

  1 * (probability of finding page on the first dice roll)
+ 2 * (probability of finding page on the second dice roll)
+ ...

そして、はい、合計は無限です。最悪のケースを考えたときに、任意の数のサイコロを振ることができると判断したからです。計算できないという意味ではありません（計算できないという意味かもしれませんが、計算する必要はありません）。

最初の試行でページが見つかる確率はです1/100。2番目のサイコロの目でそれを見つける確率はどれくらいですか？

于 2010-01-23T09:31:32.067 に答える
2

これを分析するには、実際に最良、最悪、平均的なケースが何であるかを考えてください。これら 3 つのケースを見つけるには、次の 3 つの質問に答える必要があります。

  1. 目的のページを見つけるためのロールの最小数は?
  2. 目的のページを見つけるためのロールの最大数は?
  3. 目的のページを見つけるまでの平均ロール数は?

最初の 2 つを見つけたら、3 つ目はそれほど難しくありません。巻数だけではなく漸近的な表記が必要な場合は、本のページ数を変更すると、各質問への回答がどのように変化するかを考えてみてください (例: 200 ページ対 100 ページ対 50 ページ)。

于 2010-01-23T08:32:04.187 に答える
1

もうすぐですが、(1 + 2 + ... + 100)/100 は 50 ではありません。

無作為に選択する方法は、デッキ全体を無作為にシャッフルしてから、ターゲットを順番に検索するのと同じであることに注意してください。各ポジションの可能性は等しいため、平均は簡単に計算できます。もちろん、すべての作業を前もって行っているわけではありませんが、各乱数を生成して対応する要素にアクセスするために必要なだけです。

本がリンクされたリストとして保存されている場合、ランダムに選択された各ページから次の選択に移動するコストは、それらがどれだけ離れているかによって異なり、分析が非常に複雑になることに注意してください。実際には、一定時間アクセスできるとは述べていません。「本物の本」がそれを提供するかどうかは、おそらく議論の余地があります.

さらに言えば、繰り返しのない乱数を選択する方法は複数あり、すべてが同じ実行時間になるわけではありません。

したがって、「訪問したページ数」以外の観点からアルゴリズムを分析するには、より詳細な情報が必要になります。

于 2010-01-23T14:05:17.167 に答える