Экспоненциальный поиск

Экспоненциальный поиск
Сорт	Алгоритм поиска
Структура данных	Множество
Худшая производительность	О (логарифм i )
Лучшая производительность	О (1)
Средняя производительность	О (логарифм i )
Наихудшая пространственная сложность	О (1)
Оптимальный	Да

В информатике — экспоненциальный поиск (также называемый поиском с удвоением , галопирующим поиском или поиском Струзика ). ^{[ 1 ]} — это алгоритм , созданный Джоном Бентли и Эндрю Чи-Чи Яо в 1976 году для поиска отсортированных, неограниченных/бесконечных списков. ^{[ 2 ]} Существует множество способов реализовать это, наиболее распространенным из которых является определение диапазона, в котором находится ключ поиска, и выполнение двоичного поиска в этом диапазоне. Для этого требуется O (log i ), где i — позиция ключа поиска в списке, если ключ поиска находится в списке, или позиция, в которой должен находиться ключ поиска, если ключа поиска нет в списке.

Экспоненциальный поиск также можно использовать для поиска в ограниченных списках. Экспоненциальный поиск может даже превзойти более традиционные поиски по ограниченным спискам, такие как двоичный поиск, когда искомый элемент находится рядом с началом массива. Это связано с тем, что экспоненциальный поиск будет выполняться за время O (log i ), где i — индекс искомого элемента в списке, тогда как двоичный поиск будет выполняться за O (log n время ), где n — количество элементов. в списке.

Алгоритм

Экспоненциальный поиск позволяет осуществлять поиск в отсортированном неограниченном списке по указанному входному значению («ключ поиска»). Алгоритм состоит из двух этапов. На первом этапе определяется диапазон, в котором находился бы ключ поиска, если бы он находился в списке. На втором этапе по этому диапазону выполняется бинарный поиск. На первом этапе, предполагая, что список отсортирован в порядке возрастания, алгоритм ищет первый показатель степени j , где значение 2 ^дж больше, чем ключ поиска. Это значение, 2 ^дж становится верхней границей двоичного поиска с предыдущей степенью 2, 2 ^{й - 1}, являющийся нижней границей бинарного поиска. ^{[ 3 ]}

// Returns the position of key in the array arr of length size.
template <typename T>
int exponential_search(T arr[], int size, T key)
{
    if (size == 0) {
        return NOT_FOUND;
    }

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

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

На каждом этапе алгоритм сравнивает значение ключа поиска со значением ключа в текущем индексе поиска. Если элемент по текущему индексу меньше ключа поиска, алгоритм повторяется, переходя к следующему индексу поиска, удваивая его, и вычисляя следующую степень 2. ^{[ 3 ]} Если элемент по текущему индексу больше ключа поиска, алгоритм теперь знает, что ключ поиска, если он вообще содержится в списке, находится в интервале, образованном предыдущим индексом поиска, 2 ^{й - 1}, и текущий индекс поиска, 2 ^дж. Затем выполняется двоичный поиск с результатом либо неудачи, если ключа поиска нет в списке, либо позиции ключа поиска в списке.

Производительность

Первый этап алгоритма занимает время O (log i ), где i — индекс, в котором ключ поиска будет находиться в списке. Это связано с тем, что при определении верхней границы бинарного поиска цикл while выполняется точно $\lceil \log(i)\rceil$ раз. Поскольку список отсортирован, после удвоения индекса поиска $\lceil \log(i)\rceil$ раз алгоритм будет использовать индекс поиска, который больше или равен i , как $2^{\lceil \log(i)\rceil }\geq i$ . Таким образом, первый этап алгоритма занимает время O (log i ).

Вторая часть алгоритма также занимает время O (log i ). Поскольку второй этап представляет собой просто двоичный поиск, он требует O (log n ), где n — размер интервала поиска. Размер этого интервала будет равен 2 ^дж - 2 ^{й - 1} где, как видно выше, j = log i . Это означает, что размер искомого интервала равен 2 ^{войти я} - 2 ^{войти я - 1} = 2 ^{войти я - 1}. Это дает нам время выполнения журнала (2 ^{войти я - 1}) = журнал ( я ) - 1 = О ( журнал я ).

Это дает алгоритму общее время выполнения, рассчитанное путем суммирования времени выполнения двух этапов, равное O (log i ) + O (log i ) = 2 O (log i ) = O (log i ).

Альтернативы

Бентли и Яо предложили несколько вариантов экспоненциального поиска. ^{[ 2 ]} Эти варианты заключаются в выполнении двоичного поиска в отличие от унарного поиска при определении верхней границы двоичного поиска на втором этапе алгоритма. Это разбивает первый этап алгоритма на две части, что делает алгоритм в целом трехэтапным. Новый первый этап определяет значение $j'$ , как и раньше, так что $2^{j'}$ больше, чем ключ поиска и $2^{j'/2}$ ниже, чем ключ поиска. Ранее, $j'$ определялось унарным образом путем вычисления следующей степени 2 (т. е. путем добавления 1 к j ). В варианте предлагается $j'$ вместо этого удваивается (например, прыжок с 2 ² до 2 ⁴ в отличие от 2 ³). Первый $j'$ такой, что $2^{j'}$ больше, чем ключ поиска, образует гораздо более грубую верхнюю границу, чем раньше. Как только это $j'$ найден, алгоритм переходит ко второму этапу и выполняется двоичный поиск на интервале, образованном $j'/2$ и $j'$ , давая более точную верхнюю границу показателя j . Отсюда третий этап алгоритма выполняет двоичный поиск на интервале 2. ^{й - 1} и 2 ^дж, как и раньше. Производительность этого варианта $\lfloor \log i\rfloor +2\lfloor \log(\lfloor \log i\rfloor +1)\rfloor +1$ = О (логарифм i ).

Бентли и Яо обобщают этот вариант до варианта, в котором любое количество k двоичных поисков выполняется на первом этапе алгоритма, что дает k -вложенный вариант двоичного поиска. Асимптотическое время выполнения не меняется для вариаций, выполняемых за время O (log i ), как в исходном алгоритме экспоненциального поиска.

Кроме того, структура данных с жесткой версией свойства динамического пальца может быть задана, когда приведенный выше результат k -вложенного двоичного поиска используется в отсортированном массиве. ^{[ 4 ]} Используя это, количество сравнений, выполненных во время поиска, равно log ( d ) + log log ( d ) + ... + O (log ^*d ), где d — разница в ранге между последним элементом, к которому осуществлялся доступ, и текущим элементом, к которому осуществляется доступ.

Приложения

Алгоритм, основанный на экспоненциальном увеличении полосы поиска, решает глобальное парное выравнивание за O(ns) , где n — длина последовательностей, а s — расстояние редактирования между ними. ^{[ 5 ]}^{[ 6 ]}

См. также

Ссылки

^ Баэса-Йейтс, Рикардо ; Сэлинджер, Алехандро (2010), «Алгоритмы быстрого пересечения отсортированных последовательностей», в Эломаа, Тапио; Маннила, Хейкки ; Орпонен, Пекка (ред.), Алгоритмы и приложения: очерки, посвященные Эско Укконену по случаю его 60-летия , Конспект лекций по информатике, том. 6060, Springer, стр. 45–61, Bibcode : 2010LNCS.6060...45B , doi : 10.1007/978-3-642-12476-1_3 , ISBN 9783642124754 .
^ Перейти обратно: ^а ^б Бентли, Джон Л .; Яо, Эндрю К. (1976). «Почти оптимальный алгоритм неограниченного поиска». Письма об обработке информации . 5 (3): 82–87. дои : 10.1016/0020-0190(76)90071-5 . ISSN 0020-0190 .
^ Перейти обратно: ^а ^б Йонссон, Хокан (19 апреля 2011 г.). «Экспоненциальный двоичный поиск» . Архивировано из оригинала 01 июня 2020 г. Проверено 24 марта 2014 г.
^ Андерссон, Арне; Торуп, Миккель (2007). «Динамические упорядоченные множества с экспоненциальными деревьями поиска». Журнал АКМ . 54 (3): 13. arXiv : cs/0210006 . дои : 10.1145/1236457.1236460 . ISSN 0004-5411 . S2CID 8175703 .
^ Укконен, Эско (март 1985 г.). «Нахождение примерных закономерностей в строках» . Журнал алгоритмов . 6 (1): 132–137. дои : 10.1016/0196-6774(85)90023-9 . ISSN 0196-6774 .
^ Шошич, Мартин; Шикич, Майл (23 августа 2016 г.). «Edlib: библиотека C/C++ для быстрого и точного выравнивания последовательностей с использованием расстояния редактирования» . дои : 10.1101/070649 . S2CID 3818517 .

[Baeza-Yates-1] Баэса-Йейтс, Рикардо ; Сэлинджер, Алехандро (2010), «Алгоритмы быстрого пересечения отсортированных последовательностей», в Эломаа, Тапио; Маннила, Хейкки ; Орпонен, Пекка (ред.), Алгоритмы и приложения: очерки, посвященные Эско Укконену по случаю его 60-летия , Конспект лекций по информатике, том. 6060, Springer, стр. 45–61, Bibcode : 2010LNCS.6060...45B , doi : 10.1007/978-3-642-12476-1_3 , ISBN 9783642124754 .

[PaperBentley-2] Перейти обратно: ^а ^б Бентли, Джон Л .; Яо, Эндрю К. (1976). «Почти оптимальный алгоритм неограниченного поиска». Письма об обработке информации . 5 (3): 82–87. дои : 10.1016/0020-0190(76)90071-5 . ISSN 0020-0190 .

[NotesJonsson-3] Перейти обратно: ^а ^б Йонссон, Хокан (19 апреля 2011 г.). «Экспоненциальный двоичный поиск» . Архивировано из оригинала 01 июня 2020 г. Проверено 24 марта 2014 г.

[PaperAndersson-4] Андерссон, Арне; Торуп, Миккель (2007). «Динамические упорядоченные множества с экспоненциальными деревьями поиска». Журнал АКМ . 54 (3): 13. arXiv : cs/0210006 . дои : 10.1145/1236457.1236460 . ISSN 0004-5411 . S2CID 8175703 .

[5] Укконен, Эско (март 1985 г.). «Нахождение примерных закономерностей в строках» . Журнал алгоритмов . 6 (1): 132–137. дои : 10.1016/0196-6774(85)90023-9 . ISSN 0196-6774 .

[6] Шошич, Мартин; Шикич, Майл (23 августа 2016 г.). «Edlib: библиотека C/C++ для быстрого и точного выравнивания последовательностей с использованием расстояния редактирования» . дои : 10.1101/070649 . S2CID 3818517 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]