質問: 線形検索を考えてみてください。検索対象の要素が配列内の任意の要素である可能性が等しいと仮定すると、入力シーケンスの平均でいくつの要素をチェックする必要がありますか?
これを解決するにはどうすればよいですか？要素がシーケンスに存在しない場合を考慮する必要がありますか? その場合、すべての n 要素をチェックする必要があります。
総数 のケースがございます(n + 1)。したがって、平均No. チェックする要素数 = (1 + ... + n + n) / (n + 1). この答えは正しいですか？
要素が配列内にある場合 (検索の成功) とそうでない場合 (検索の失敗) の 2 つのケースを区別します。
成功した検索の平均は (1 + 2 + ... + n) / n = (n + 1) / 2 です。
失敗した検索の場合、平均はちょうど n です。
合計平均は、成功した検索と失敗した検索の組み合わせに依存するようになりました。たとえば、ほとんどの検索が失敗した場合、n に近くなります。すべての検索が成功した場合 (これが質問の意味のようです)、平均は (n + 1) / 2 です。
検索が成功する確率が p である場合、検索が失敗する確率は 1-p であり、p * (n+1) / 2 + (1-p) * n の平均が得られます。