Интерполяционный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Другая картинка)
Строка 3: Строка 3:
  
 
== Алгоритм ==
 
== Алгоритм ==
[[Файл:Interpolation_search.png|thumb|350px|Нахождение разделительного элемента]]
+
[[Файл:Interpolation_search.png|thumb|350px|right|Нахождение разделительного элемента]]
 
Пусть <tex> a </tex> {{---}} отсортированный массив чисел из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
 
Пусть <tex> a </tex> {{---}} отсортированный массив чисел из <tex> n </tex> чисел, <tex> x </tex> {{---}} значение, которое нужно найти. Поиск происходит подобно [[Целочисленный двоичный поиск|двоичному поиску]], но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что <tex> x </tex> лежит между <tex> a_l </tex> и <tex> a_r </tex>, то следующая проверка выполняется примерно на расстоянии <tex dpi = "170"> \frac{x - a_l}{a_r - a_l} \cdot</tex> <tex> (r - l) </tex> от <tex> l </tex>.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
 
+
<code style = "display: inline-block;">
<code>
 
 
  interpolationSearch(n, x):
 
  interpolationSearch(n, x):
 
   l = 0; // левая граница поиска (будем считать, что элементы массива нумеруются с нуля)
 
   l = 0; // левая граница поиска (будем считать, что элементы массива нумеруются с нуля)
Строка 26: Строка 25:
 
   else
 
   else
 
     result = -1; // not found
 
     result = -1; // not found
</code>
+
</code>
  
 
== Время работы ==
 
== Время работы ==

Версия 13:04, 29 мая 2012

Идея

Рассмотрим задачу: найти слово в словаре. Если оно начинается на букву "А", то никто не будет искать его в середине, а откроет словарь ближе к началу. В чём разница между алгоритмом человека и другими? Отличие заключается в том, что алгоритмы вроде двоичного поиска не делают различий между "немного больше" и "существенно больше".

Алгоритм

Нахождение разделительного элемента

Пусть [math] a [/math] — отсортированный массив чисел из [math] n [/math] чисел, [math] x [/math] — значение, которое нужно найти. Поиск происходит подобно двоичному поиску, но вместо деления области поиска на две примерно равные части, интерполирующий поиск производит оценку новой области поиска по расстоянию между ключом и текущим значением элемента. Если известно, что [math] x [/math] лежит между [math] a_l [/math] и [math] a_r [/math], то следующая проверка выполняется примерно на расстоянии [math] \frac{x - a_l}{a_r - a_l} \cdot[/math] [math] (r - l) [/math] от [math] l [/math].

Псевдокод

interpolationSearch(n, x):
  l = 0; // левая граница поиска (будем считать, что элементы массива нумеруются с нуля)
  r = n - 1; // правая граница поиска

  while a[l] <= x && x <= a[r]
    m = l + (x - a[l]) / (a[r] - a[l]) * (r - l); // элемент, с которым будем проводить сравнение
    if a[m] == x
      result = m;
    if a[m] < x
      l = m + 1;
    else
      r = m - 1;

  if a[l] == x
    result = l;
  else
    result = -1; // not found

Время работы

Асимптотически интерполяционный поиск превосходит по своим характеристикам бинарный. Если ключи распределены случайным образом, то за один шаг алгоритм уменьшает количество проверяемых элементов с [math] n [/math] до [math] \sqrt n [/math]. То есть, после [math]k[/math]-ого шага количество проверяемых элементов уменьшается до [math]n^{\frac{1}{2^k}}[/math]. Значит, остаётся проверить только 2 элемента (и закончить на этом поиск), когда [math]\frac{1}{2^k} = log_{n}2 = \frac{1}{log_{2}n} [/math]. Из этого вытекает, что количество шагов, а значит, и время работы составляет [math]O(\log \log n)[/math].

При "плохих" исходных данных (например, при экспоненциальном возрастании элементов) время работы может ухудшиться до [math] O(n) [/math].

Эксперименты показали, что интерполяционный поиск не настолько снижает количество выполняемых сравнений, чтобы компенсировать требуемое для дополнительных вычислений время (пока таблица не очень велика). Кроме того, типичные таблицы недостаточно случайны, да и разница между значениями [math]\log \log n[/math] и [math]\log n[/math] становится значительной только при очень больших [math]N[/math]. На практике при поиске в больших файлах оказывается выгодным на ранних стадиях применять интерполяционный поиск, а затем, когда диапазон существенно уменьшится, переходить к двоичному.

Литература

Д.Э. Кнут: Искусство программирования (том 3)

Wikipedia: Interpolation search

Wikipedia: Интерполирующий поиск