誤謬発見効率の良い検索方法
誤謬発見効率の良い検索方法
下記条件の下で、数列Xについて、誤謬要素発見に要する時間の期待値が最も少ない検索方法を教えてください。もしくは、勉強の糸口となるような情報(該当する分野、本など)を教えてください。
1. 要素数nの規則性のない数列X(x_1, x_2, ..., x_n)がある。
2. 1個以上の要素が誤っていることは分かっている。以下、この要素を誤謬要素と呼ぶことにする。
3. 全ての誤謬要素を特定するのが目標である。但し、誤謬要素はそれほど多くなく、存在個数の確率分布は、平均値n/20程度のポアソン分布に従うと考える。
4. i番目からj番目までの連続した要素について、誤謬要素の有無について判定する関数F[i, j]を持つ。
5. 関数Fを用いる以外の方法では、誤謬要素を発見できない。
6. 関数Fを一度実行するのに必要な時間は、a(定数)である。
現在やっている方法は、直感的に効率が良さそうな以下の方法です。しかし、私としてはより速い方法を行い、且つそれが効率が良いという点について理論的な確証を得たいと考えています。
F[1,n/2], F[n/2+1, n]を行い、誤謬要素がある方について、更に検索範囲を半分にして関数Fで判定する。
補足
以下に示されていない状況で、補足情報が必要な場合は、質問者に補足要求する前に、回答者が場合分けしてお答えください。場合分けが8通り以上に及ぶ場合は、質問状況を絞りますので、補足要求してください。
お礼
有難うございます