Почему среднее число сравнений k-арного поиска составляет k* ln(N) / ln(k)?

Question

Я знаю, что функция выполняется ln(N)/ln(K) раз, но в среднем она делает K операций?

Вопросы:

есть ли доказательства того, что k*ln(N)/ln(K) - это среднее число казней?
Если эта формула верна, то троичный поиск будет самым быстрым поиском, так как k/ln(k) будет минимальным (для целых чисел), потому что 3 является ближайшим целым числом к "e" (действительный минимум), что очень легко доказать с помощью дифференциация.

Кроме того, я считаю, что троичный поиск быстрее, потому что я сделал сравнительную компьютерную программу.

algorithm data-structures binary-tree binary-search ternary-search

Источник

user1205603 13 фев '12 в 11:16

1 ответ

Другие вопросы по тегам algorithm data-structures binary-tree binary-search ternary-search

user1206731 13 фев '12 в 12:08 2012-02-13 12:08 · Answer 1 · 2012-02-13 12:08

Нет, потому что правильный ответ (k - 1) log n / log k + O(1): только k - 1 сравнений (на самом деле только lg k + O(1)) необходимы для уменьшения размера диапазона поиска на фактор к. Это можно доказать по индукции по рекуррентности T(1) = 1, T(2) = 2, T(n) = (k - 1) + T(n / k).
Целое число argmin (k - 1) / log k встречается в 2. Существует множество компьютерных архитектурных причин, по которым троичный поиск в любом случае может быть быстрее.