algorithm - 黄金分割探索は二分探索よりも優れていますか？

Question

最近、範囲を2ではなくファイ（黄金比）で分割することで二分探索が改善されるかもしれないという意見を聞きました。そのような最適化について聞いたことがないので、これは私にとって大きな驚きでした。これは本当ですか？2による除算とファイによる除算が同等のパフォーマンスであった場合、これは真実でしたか？

そうでない場合、黄金分割探索が二分探索よりも高速に実行される一般的な条件はありますか？

UPD：関連性のないウィキペディアの記事へのリンクを削除するように編集されました。誤解を招く恐れがあります。

Answer 1

「フィボナッチ検索」と呼ばれる2つのアルゴリズムがあります。

リンクした記事は、特定の関数の最大値または最小値を見つけるための数値アルゴリズムに関するものです。これは、この問題に最適なアルゴリズムです。この問題は、二分探索の問題とは十分に異なるため、適切な特定のケースでは明らかです。

他の種類のフィボナッチ検索は、二分探索と同じ問題を攻撃します。二分探索は本質的に常に優れています。Knuthは、フィボナッチ検索は「2で除算するのではなく、足し算と引き算だけを行うため、一部のコンピューターで推奨されます」と書いています。しかし、ほとんどすべてのコンピューターは2進演算を使用しており、2による除算は加算と減算よりも簡単です。

（ウィキペディアの記事は現在、フィボナッチ検索の参照の局所性が優れている可能性があると主張していますが、クヌースは主張していません。おそらく、これは誤解を招く可能性があります。範囲を絞り込むのにあまり役立ちません。平均すると、テーブルのより多くの部分からの読み取りが多くなり、少なくなることはありません。レコードが実際にテープに保存されているため、シーク時間が支配的である場合、フィボナッチ検索はバイナリ検索よりも優れている可能性があります。その場合、両方のアルゴリズムは最適とはほど遠いです。）

Answer 2

ここで何かが足りないかもしれませんが、黄金分割探索のWikipediaエントリを見ると、バイナリ検索と同じ問題はまったく解決されていないようです。バイナリ検索はソートされたリストの値を見つけるのに役立ちますが、黄金分割探索は、値の範囲にわたる関数の最小値または最大値を見つけるために使用されます。

Answer 3

「より速く動作する」はあいまいです。ただし、バイナリ検索では、アクセス数の最悪のケースを最小にする必要があります。