-2

配列が与えられ、結果として生じる任意の 2 つの要素間の距離は 1 (+1 または -1) です。私たちは番号で与えられます。数値が配列内にあるかどうかを最小限の複雑さで確認するにはどうすればよいですか。

4

6 に答える 6

1

この問題は、セル プローブの複雑さ Ω(n) を想定しているため、サブリニア アルゴリズムは発生しません。可能な入力を検討する

210101010...10
012101010...10
010121010...10
...
010101010...12

等確率で。2 を見つけます。Yao の補題により、入力分布が固定されている場合、最適なランダム化アルゴリズムは、最適な決定論的アルゴリズムよりも優れているわけではありません。2 を見つける前は、除外されていない入力はすべて同一に見えます。したがって、すべての正しい決定論的アルゴリズムは、ある順序で 0 の場所を調査する必要があり、2 が見つかるまで予想される n/4 (またはその付近) の場所が調査されます。

于 2013-07-16T12:48:38.923 に答える
0

v配列内の値を探すとしましょう。指定された位置iでの値a[i]がv-d探している値である場合、少なくともdからセルの距離にありiます。v-d+1したがって、間にあるセルをスキップできますv-d+2。したがって、ここにずさんな再帰アルゴリズムがあります。

template <class ForwardIter, class T>
ForwardIter find_in_singlestep_range(ForwardIter first, ForwardIter last, T val) {
  if (first == last) return last;
  if (*first == val) return first;

  auto max_diff = last-first;
  auto diff = make_signed<T>{val} - make_signed<T>{*first};
  if (diff < 0) diff = -diff;
  if (diff > max_diff) return last;

  return find_in_singlestep_range(first+diff, last, val);
}

複雑さ: 要素に遭遇しないと仮定すると、最悪の場合は diff が 1,2,2,2,2 になる可能性があるため、最大で 1/2*N +1 回の比較が得られるため、2 つおきの要素をスキップします。(diff が 2 の場合、次の diff は 2 または 4 になります。)

二分探索を行うと、より複雑になる可能性があります。サブ配列の中間要素とvalサブ配列のサイズの半分より大きい場合、サブ配列の検索をスキップできます。

于 2013-07-16T13:34:37.390 に答える
0

もちろん、複雑さを O(N) より小さくすることはできません。つまり、配列全体を調べます。

いつでも

  • 読み取り値から目的の数を引いた値が、絶対値で、OR に続く要素の数よりも大きい
  • 読み取った値が目的の値に等しい

私は答えとして「はい」と言ってアルゴリズムを「壊す」でしょう。

デフォルトでは、答えは「いいえ」です。:)

于 2013-07-16T12:19:51.297 に答える