問題タブ [ternary-search]

重複の可能性:
C の三分探索

三次[三次]検索プログラムを書きます。

注: 三次検索は二分検索に似ています。二分探索では、配列の 2 つの部分を考慮し、次の検索空間として 1 つの部分を選択します。三次探索では、配列を 3 つの等しい部分で検討します。このために、配列の 1/3 と 2/3 でそれぞれ middle1 と middle2 という 2 つの "中間" インデックスを取得します。次に、3 つのパーツのいずれかを選択し、その中で検索を続けます。

また、最悪の場合の三項探索の時間計算量はどうすればわかりますか?

私の試み：

検索する番号が (配列の) 最後の 2 ～ 3 か所のいずれかに存在する場合、終了します。どこで間違いを犯したのですか？

三項探索アルゴリズムは、増加してから減少する関数、または減少してから増加する関数である単峰関数の最小値または最大値を見つけるための高速アルゴリズムです。減少してから増加する関数を扱っており、値の最小値を見つけたいと仮定します。三項検索は、次の再帰を使用して機能します。

• ウィンドウのサイズが「十分に小さい」場合は、その中間点を返します。
• さもないと：
  • 左右の境界で関数を評価します。値を l および r と呼びます。
  • 1/3 点と 2/3 点で関数を評価します。値を m ₁および m _{2と呼びます}
  • m ₁ < m _{2の場合、関数の増加領域にあり、最小値は m 2}と rの間にありません。
  • m ₁ > m ₂の場合、関数の減少領域にあり、最小値が l と m _{1の間にあることはできません}
  • 破棄されなかった 2/3 を再帰的に検索します。

このアルゴリズムは、反復ごとに 1/3 の値を捨て続けることができるため、迅速に機能します。

ただし、このアルゴリズムをより高速に実行できると信じているため、何かが欠けているように感じます。特に、境界とプローブ ポイントの 1 つとの間の範囲の 3 分の 1 を常に除外していることに注意してください。これは、プローブ ポイントと他の境界の間の領域を保持することを意味します。三分探索は 1/3 ポイントでプローブ ポイントを選択するため、これは、各ポイントで値の 2/3 を保持することを意味します。1/3 と 2/3 のポイントでプローブする代わりに、1/2 - ε と 1/2 + ε のポイントでプローブして、非常に小さい ε を求めたらどうなるでしょうか? これは、各ステップで範囲の 1/2 - ε を破棄することを意味します。これは、毎回要素の 1/3 を単に破棄する場合よりも、範囲のサイズがはるかに速く減少することを意味します。

例として、ε = 1/1000 を選択すると、各反復で検索する範囲の 999/2000 を破棄することになります。いくつかの反復の後に残っている部分がここに示されています (三項探索は左側にあり、私のアルゴリズムは右側にあります:)

この修正版のアルゴリズムは、元のバージョンよりも「優れている」だけですか? それとも、プローブ ポイントを選択するために変更された戦略を使用すべきではないことを意味する、ここで欠けているものはありますか?

関数が ln(N)/ln(K) 回実行されることはわかっていますが、平均して K 回の操作が行われますか?

質問:

1. k*ln(N)/ln(K) が平均実行回数であるという証拠はありますか?
2. この式が正しければ、k/ln(k) が (整数の場合) 最小になるため、3 項検索が最速の検索になります。差別化。

さらに、比較プログラムを作ったので、三項探索の方が速いと思います。

下に「test」という関数があります。私のプログラムはテスト関数に合格できません。

これは三項検索の私のコードです。三分探索は二分探索に似ていますが、すべての要素を 2 で割るのではなく、3 で割ります。

三項検索を使用するために、アイテムの 1/3 の分割に index2 を使用しました。index1 は、アイテムの 2/3 の分割線です。

「高」と「低」を index1 または index2 に割り当てるだけです。これにより、リストを 3 つの部分に分割できます。ハイとローは、分割されたリストのどの部分を検索するかを見つけるために機能します。次に、高値と低値が互いに近づくまで、このプロセスが繰り返されます。

seq はリスト内の項目です。[1,2,3,4,5...] リストの項目は順番に並んでいます。

キーは私が探している値です

および ternary_search は、キーのインデックスまたはキーに近い数値のインデックスを返します

楽しむ！乾杯！

私はこの問題を解決しようとしています: http://acm.tju.edu.cn/toj/showp2886.html

いくつかの解決策を試しましたが、そのうちの 2 つについて説明します。両方とも、コスト (位置) が凸関数であると仮定していることに注意してください。つまり、中央に向かって減少し (実際には、中央値 (供給ポイント) に向かってどこか)、グラフは多かれ少なかれ U 字型のように見えます。

1. cost(position) <= M である供給ポイントの左端と右端の位置を見つけます。最小値と最大値を見つけた後、間隔を少し大きくできるかどうかを確認します (レストランは場所である必要はないため)。正確に供給ポイントに）。これは良い解決策ですが、最後のビットを計算するのに非常に時間がかかります。M が非常に大きく、最小コストの供給ポイントがほとんどないテストでは失敗します。複雑さ: O(NlogN) + O(M)。以下のこの解決策はそのままで時間制限を超えていますが、O(1) で両方向にどれだけ移動できるかを計算する別の解決策を試してみましたが、間違った答えが得られました。

2. この関数は凸関数であるため、三項検索を使用して最小値を見つけることができます。最小値が M 未満の場合、関数の下限と上限 (つまり M) をバイナリ検索します。複雑さ: O(NlogM) すべての O(logM) に対して、O(N) でコストを計算するためです。

これは私が試したものであり、まだ「間違った答え」が得られるので、これが私を狂わせているので、助けが必要です.

最初にそれを読んだとき、コストがすべての供給ポイントから計算されたのではなく、最も近いものから計算されたと思ったので、問題は仕様で実際には明確ではありません (少なくとも私はそう思います)。例はそれをクリアしました。また、コスト（位置）関数が凸であるという私の仮定が本当に正しいかどうかもわかりません。しかし、私は多くの例を試しましたが、そうです。

ありがとう。どんな助けでも大歓迎です。:D

時間と空間の複雑さの点で、二分探索は三分探索より優れていますか?

Aをn個の正の整数の配列とします。

次のようなA のインデックスkを見つけるにはどうすればよいですか。

絶対差が最小である (つまり、abs(left - right)最小である) ?

この差の絶対関数は放物線（最小差まで減少し、Uのように増加する）であるため、このような関数（放物線）で値を見つけるために三分探索が使用されると聞きましたが、方法がわかりません私はインターネットで検索しましたが、放物線関数に対する三項検索の使用法が見つからなかったので、それを実装してください。

編集: O(1) ですべての間隔の合計があり、O(n) よりも高速なものが必要だとします。そうでない場合は、三分探索は必要ありません..