k-ary検索の平均比較がk * ln（N）/ ln（k）であるのはなぜですか？

私は関数がln（N）/ ln（K）回実行されることを知っていますが、平均してK演算を行いますか？k-ary検索の平均比較がk * ln（N）/ ln（k）であるのはなぜですか？

質問：

のk *のLN（N）/ LN（K）の実行の平均数であることを、任意の証明がありますか？
この式が正しければ、3が最も簡単な「e」（実際の最小値）に最も近いため、k/ln（k）が最小値（整数）として3次探索が最も速い検索になります差別化を利用することを証明する

さらに、私は比較コンピュータプログラムを作ったので、3進検索がより速いと信じています。

はい3進数は 'e'に近いため、高速です。しかし、コンピュータはバイナリで高速です。あなたは三元のコンピュータを持っていれば3を望むでしょう。 –

あなたの質問の第二部分について議論されています[ここ]（http://stackoverflow.com/questions/3498382/why-use-binary-search-if-theres-三元探索）。 – dasblinkenlight

いいえ、正解は（K - 1）であるため、N/K + O（1）ログログ： - 1の比較（実際には（1）K + OをLG）を低減するために必要なだけkが探索範囲の大きさをk倍にする。これは、再帰T（1）= 1、T（2）= 2、T（n）=（k-1）+ T（n/k）の誘導によって証明することができる。
（k-1）/ log kの整数argminは2で発生します。なぜなら、3値検索が高速になる理由はたくさんあります。

2012-02-13 12:08:54 wat

答えて