Здравствуйте уважаемые читатели. Я расскажу об одном из численных методов, который может быть применен к задаче поиска в отсортированном односвязном или двухсвязном списках.
Пусть N — количество элементов в списке. Поиск элемента в упорядоченном по возрастанию списке может быть осуществлен линейным методом поиска (перебор), бинарным методом поиска и используя хеширование. О хешировании говорить не буду, так как это отдельная тема, а вот два других метода поиска стоит покритиковать.
Для линейного метода основным недостатком является порядок количества сравнений — O(N), в среднем выполняется N/2 сравнений и проходов на следующий элемент списка.
Для бинарного метода поиска количество сравнений соответствует O(logN), но при этом количество проходов на следующий элемент списка больше, чем у линейного, что связанно с необходимостью передвигаться по списку на средний элемент из диапазона. Этот метод делает лишние передвижения по списку.
Естественно хотелось бы иметь метод, который двигается вперед по списку без лишних проходов, как линейный метод, но имел бы количество сравнений порядка O(logN), как бинарный метод. Таковым методом является метод итераций, который многие наверняка изучали в курсе численных методов. Метод итераций применяется для поиска нуля непрерывных функций, поэтому его необходимо адаптировать к списку, который можно рассматривать как дискретную функцию (индекс и значение). Для работы метода потребуется рассмотреть формулу, по которой он работает для непрерывной функции:
xn+1=G(xn),
где G — сжимающая функция, xn — решение на n-ом шаге для задачи f(x)=0.
Но наша задача заключается в поиске элемента key или его индекса x, при котором f(x)=key. Запишем f(x)=key в виде f(x)-key=0 и получим возможность применять численные методы поиска нуля функции. В дальнейшем обращение к любому элементу списка потребует вычитание key. Для непрерывных функций функция сжатия имеет вид G(x):
G(x)=x-f(x)/f'(x),
а формула для получения следующего индекса:
xn+1=xn-f(xn)/f'(xk)
В выражении f'(xk) k может быть равным n (метод Ньютона), а может быть фиксированным (метод итераций).
Для дискретного случая для метода итераций получим:
xn+1=xn-f(xn)/max{|f(xk+1)-f(xk)|, k=0,N-2}
с учетом вычитания key при обращении к функции:
xn+1=xn-(f(xn)-key)/max{|f(xk+1)-f(xk)|, k=0,N-2}
или в компактном виде:
С=1/max{|f(xk+1)-f(xk)|, k=0,N-2}
xn+1=xn-(f(xn)-key)*C
или
xn+1=xn+(key-f(xn))*C
«С» рассчитывается один раз до применения поиска, и может быть пересчитан при добавлении новых элементов в список. Выражение (key-f(xn))*C показывает на сколько элементов можно продвинуться вперед не использую прямых проверок на совпадение, как это делает линейный метод, но при этом не позволит пропустить искомый элемент. Округление (key-f(xn))*C производится в большую сторону.
Пример бок-схемы алгоритма поиска в списке методом итераций:
Метод итераций можно также использовать в отсортированных массивах, но для этого контейнера его эффективность по сравнению с бинарным методом ниже. Применение данного метода оправдано в контейнерах с последовательным доступом, где бинарный метод мало эффективен или не применим вообще. У метода есть недостатки — вырождение в линейный метод при условии f(xi+2)-f(xi+1)>f(xi+1)-f(xi) для каждого i от 0 до N-3.
Метод Ньютона и хорд также возможно применять для задачи поиска в массиве или списке, но об этом в следующий раз.
Пусть N — количество элементов в списке. Поиск элемента в упорядоченном по возрастанию списке может быть осуществлен линейным методом поиска (перебор), бинарным методом поиска и используя хеширование. О хешировании говорить не буду, так как это отдельная тема, а вот два других метода поиска стоит покритиковать.
Для линейного метода основным недостатком является порядок количества сравнений — O(N), в среднем выполняется N/2 сравнений и проходов на следующий элемент списка.
Для бинарного метода поиска количество сравнений соответствует O(logN), но при этом количество проходов на следующий элемент списка больше, чем у линейного, что связанно с необходимостью передвигаться по списку на средний элемент из диапазона. Этот метод делает лишние передвижения по списку.
Естественно хотелось бы иметь метод, который двигается вперед по списку без лишних проходов, как линейный метод, но имел бы количество сравнений порядка O(logN), как бинарный метод. Таковым методом является метод итераций, который многие наверняка изучали в курсе численных методов. Метод итераций применяется для поиска нуля непрерывных функций, поэтому его необходимо адаптировать к списку, который можно рассматривать как дискретную функцию (индекс и значение). Для работы метода потребуется рассмотреть формулу, по которой он работает для непрерывной функции:
xn+1=G(xn),
где G — сжимающая функция, xn — решение на n-ом шаге для задачи f(x)=0.
Но наша задача заключается в поиске элемента key или его индекса x, при котором f(x)=key. Запишем f(x)=key в виде f(x)-key=0 и получим возможность применять численные методы поиска нуля функции. В дальнейшем обращение к любому элементу списка потребует вычитание key. Для непрерывных функций функция сжатия имеет вид G(x):
G(x)=x-f(x)/f'(x),
а формула для получения следующего индекса:
xn+1=xn-f(xn)/f'(xk)
В выражении f'(xk) k может быть равным n (метод Ньютона), а может быть фиксированным (метод итераций).
Для дискретного случая для метода итераций получим:
xn+1=xn-f(xn)/max{|f(xk+1)-f(xk)|, k=0,N-2}
с учетом вычитания key при обращении к функции:
xn+1=xn-(f(xn)-key)/max{|f(xk+1)-f(xk)|, k=0,N-2}
или в компактном виде:
С=1/max{|f(xk+1)-f(xk)|, k=0,N-2}
xn+1=xn-(f(xn)-key)*C
или
xn+1=xn+(key-f(xn))*C
«С» рассчитывается один раз до применения поиска, и может быть пересчитан при добавлении новых элементов в список. Выражение (key-f(xn))*C показывает на сколько элементов можно продвинуться вперед не использую прямых проверок на совпадение, как это делает линейный метод, но при этом не позволит пропустить искомый элемент. Округление (key-f(xn))*C производится в большую сторону.
Пример бок-схемы алгоритма поиска в списке методом итераций:
Метод итераций можно также использовать в отсортированных массивах, но для этого контейнера его эффективность по сравнению с бинарным методом ниже. Применение данного метода оправдано в контейнерах с последовательным доступом, где бинарный метод мало эффективен или не применим вообще. У метода есть недостатки — вырождение в линейный метод при условии f(xi+2)-f(xi+1)>f(xi+1)-f(xi) для каждого i от 0 до N-3.
Метод Ньютона и хорд также возможно применять для задачи поиска в массиве или списке, но об этом в следующий раз.