Почему при выполнении экспоненциального поиска мы выбираем основание экспоненты равным 2?

#algorithm #search #language-agnostic

#алгоритм #Поиск #не зависит от языка

Вопрос:

Можем ли мы выбрать любую базу по нашему вкусу или база выбрана потому, что она обеспечивает максимальную эффективность?

Я рассматривал этот алгоритм. Что в основном дает это:

 template <typename T>
int exponential_search(T arr[], int size, T key) {
    if (size == 0) {
        return NOT_FOUND;
    }

    int bound = 1;
    while (bound < size amp;amp; arr[bound] < key) {
        bound *= 2;
    }


    return binary_search(arr, key, bound/2, min(bound   1, size));
}

Или эквивалент Python:

 def exponential_search(arr, p):
i = 0
while (arr[2 ** i] < p):
    i  = 1
binary_search(arr, p, i)

Как можно ясно видеть во втором цикле while, они устанавливают

 bound *=2

Почему 2? Почему не любое другое число?

1. Бессмысленно без дополнительного контекста, но, вероятно, вы смотрите на тип двоичного поиска — проблема уменьшается вдвое для каждой рекурсивной глубины, отсюда и степень 2.

2. @500-InternalServerError Я добавил еще немного контекста.

3. Вариант с основанием 3 был бы просто более сложным при небольшом выигрыше.

4. @HenkHolterman Почему это должно быть сложнее? Я думаю, это будет лучше работать с большими наборами данных?

5. Но с меньшими наборами данных можно легко справиться благодаря бинарному поиску.

Ответ №1:

Если не учитывать трудности реализации, стоимость поиска позиции n с множителем k равна log(n)/log(k) log((k-1)n) O(1) = log(n)/log(k) log(n) log(k-1) log(k-1) O(1). Увеличивая k, мы можем приблизиться к постоянному коэффициенту, но не достичь 1, однако стоимость является увеличением постоянного члена. Я полагаю, что 2 работает достаточно хорошо.

1. Извините, но не могли бы вы, пожалуйста, объяснить, как вы пришли к этой формуле сложности.

2. Кроме того, график формулы говорит, что минимум сложности составляет около k = 8.387.

3. @harshit Наилучшее k увеличивается по мере увеличения n. Формула представляет собой экспоненциальный поиск (логарифм основания k от n, первое слагаемое) плюс двоичный поиск по (k-1) n элементам.

4. Извините, я не очень знаком с этой концепцией сложности, но не следует ли вам перемножить два логарифма. Выполняется экспоненциальный поиск, а затем двоичный поиск. Разве это не должно следовать правилу Product

5. @harshit en.wikipedia.org/wiki /…