algorithm - k-ary 探索の比較の平均が k* ln(N) / ln(k) になるのはなぜですか?

Question

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

質問:

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

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

Answer 1

1. いいえ、正解は（k --1）log n / log k + O（1）であるため、検索範囲のサイズを次のように縮小するには、k -1回の比較（実際にはlg k + O（1）のみ）のみが必要です。 kの因数。これは、再発T（1）= 1、T（2）= 2、T（n）=（k-1）+ T（n / k）の誘導によって証明できます。

2. （k --1）/ log kの整数argminは2で発生します。とにかく、3値検索が高速になる可能性があるコンピュータアーキテクチャ上の理由はたくさんあります。