algorithm - 二分探索 vs 三分探索

Question

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

Answer 1

どちらにも一定のスペースがありますが、三分探索の大きな O 時間は、二分探索の Log_2 N ではなく Log_3 Nです。

実際には、各ステップで余分な比較を行う必要があるため、三分探索は使用されません。これにより、一般的に全体的により多くの比較が行われます。2 * Log_3(N) の比較と Log_2(N) の比較。

Answer 2

それはおそらくデータに依存します。より小さい比較、等しい比較、より大きい比較の数がほぼ等しい場合、データを 3 つの方法で分割することは、対数の底が 2 ではなく 3 であることを意味し、これは優れています。しかし、実際には、3 者間比較は 2 者間比較よりもコストがかかるため、一般的なケースでは、3 者間比較の追加コストはおそらく価値がありません。