Студопедия — Специальные виды поиска
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Специальные виды поиска






Интерполяционный поиск произошел от естественного поиска данных в упорядоченном массиве человеком. Если известно, что искомый ключ k находится между некоторым "нижним" ключом kl и некоторым "верхним" ключом kh,

kl < k < kh

то следующее сравнение делается на расстоянии

(l − h)(k − kl) / (kh − kl)

от текущей позиции ki. Предполагается что данные в массиве возрастают в арифметической прогрессии.

Именно по такому алгоритму выполняется поиск нужной карточки в "бумажном" библиотечном каталоге, или страницы в книге.

Этот алгоритм эффективнее бинарного поиска только в случае арифметической прогрессии, так как на каждом шаге уменьшает интервал анализа не до n/2 а до sqr(ni) и требует в среднем около log2(log2(N)) шагов, если упорядоченные данные имеют равномерное распределение.

Недостаток этого алгоритма – затраты времени на дополнительные операции при внутреннем поиске. Разность между log2(log2(N)) и log2(N) становится весьма существенной при больших N, а типичные наборы данных (которыми для этого поиска часто являются файлы) недостаточно случайны.

Этот алгоритм может быть достаточно успешным при поиске во внешних запоминающих устройствах.

Для поиска подстроки в строке могут использоваться алгоритмы Бойера–Мура (и его несколько модификаций) и Кнута–Морриса–Пратта.

 







Дата добавления: 2015-09-04; просмотров: 391. Нарушение авторских прав; Мы поможем в написании вашей работы!



Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...

Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Факторы, влияющие на степень электролитической диссоциации Степень диссоциации зависит от природы электролита и растворителя, концентрации раствора, температуры, присутствия одноименного иона и других факторов...

Йодометрия. Характеристика метода Метод йодометрии основан на ОВ-реакциях, связанных с превращением I2 в ионы I- и обратно...

Броматометрия и бромометрия Броматометрический метод основан на окислении вос­становителей броматом калия в кислой среде...

Общая и профессиональная культура педагога: сущность, специфика, взаимосвязь Педагогическая культура- часть общечеловеческих культуры, в которой запечатлил духовные и материальные ценности образования и воспитания, осуществляя образовательно-воспитательный процесс...

Устройство рабочих органов мясорубки Независимо от марки мясорубки и её технических характеристик, все они имеют принципиально одинаковые устройства...

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия