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

Question

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

Вопросы:

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

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

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 встречается в 2. Существует множество архитектурных причин, по которым троичный поиск в любом случае может быть быстрее.