単調性の性質検査

Last updated Unknown Edit Source

• 単調性 = ソートされている配列
• 全部読むわけではないので、たぶんXXという回答になる
• この場合のε-farnessの定義
  • ε: 閾値の定数$0<ε<100%$
  • $ε\times n$個以上の要素を書き換えないと単調にならなそう = ε-farである
  • 単調であるか、ε-farであるか（全く単調ではないか）を（高い確率で）判定
• 繰り返し二要素を乱択して比べるだけだと、高い確率（確信度）の結果は出せないことが計算で分かる
• そこで、二分探索を応用
  • 本来二分探索はソートされてないと動かない
  • $2ε^{-1}$回二分探索して、答えにたどり着くかどうか検証することで、単調性の検査ができる！ #性質検査