Ответ 1
Технически правильно сказать, что время выполнения двоичного поиска в двусвязном списке - O (n log n), но это не плотная верхняя граница. Используя немного лучшую реализацию бинарного поиска и более умный анализ, можно получить бинарный поиск во времени O (n).
Основная идея двоичного поиска следующая:
- Если список пуст, поиск элемента не существует.
- В противном случае:
- Посмотрите на средний элемент.
- Если он соответствует указанному элементу, верните его.
- Если это больше, чем элемент, о котором идет речь, отбросьте заднюю половину списка.
- Если это меньше, чем элемент, о котором идет речь, отбросьте переднюю половину списка.
Наивная реализация бинарного поиска в двусвязном списке будет работать, вычисляя индексы для поиска на каждой итерации (как в случае с массивом), затем обращайтесь к каждому из них, начиная с начала списка и просматривая переместите соответствующее количество шагов. Это действительно очень медленно. Если искомый элемент находится в самом конце массива, индексы, которые искали, были бы n/2, 3n/4, 7n/8 и т.д. Подводя итог работе, выполненной в худшем случае, получаем
n/2 + 3n/4 + 7n/8 + 15n/16 +... (& Theta; (log n))
& GE; n/2 + n/2 +... + n/2 (& Theta; (log n)))
= & Theta; (n log n)
и
n/2 + 3n/4 + 7n/8 + 15n/16 +... (& Theta; (log n))
& ле; n + n +... + n (& Theta; (log n)))
= & Theta; (n log n)
Следовательно, наихудшая временная сложность для этого алгоритма равна & Theta; (n log n).
Однако мы можем ускорить это с коэффициентом & theta; (log n), будучи более умным с нашим подходом. Причина, по которой предыдущий алгоритм идет медленно, заключается в том, что каждый раз, когда нам нужно искать элемент, мы начинаем поиск с начала массива. Однако нам не нужно это делать. Посмотрев средний элемент в первый раз, мы уже находимся в середине массива, и мы знаем, что следующий поиск, который мы собираемся сделать, будет либо в позиции n/4, либо в 3n/4, что только расстояние n/4 от того места, где мы остановились (по сравнению с n/4 или 3n/4, если мы начнем с начала массива). Что делать, если мы просто выходим из нашего положения остановки (n/2) в следующую позицию, а не перезапускаем в начале списка?
Вот наш новый алгоритм. Начните с сканирования до середины массива, для чего требуется n/2 шага. Затем определите, следует ли посещать элемент в середине первой половины массива или в середине второй половины массива. Достижение там позиции n/2 требует всего n/4 общих шагов. Оттуда переход в середину четверти массива, содержащего элемент, занимает всего n/8 шагов, и переход оттуда в середину восьмого массива, содержащего элемент, занимает всего n/16 шагов и т.д. Это означает что общее количество выполненных шагов дается
n/2 + n/4 + n/8 + n/16 +...
= n (1/2 + 1/4 + 1/8 +...)
& ле; п
Это следует из того, что сумма бесконечного геометрического ряда 1/2 + 1/4 + 1/8 +... равна 1. Следовательно, общая работа, выполненная в худшем случае только & Theta; (n), что намного лучше, чем раньше.
Одна деталь: зачем вам это делать? В конце концов, он уже занимает время O (n) для поиска дважды связанного списка для элемента. Одним из основных преимуществ этого подхода является то, что даже несмотря на то, что время выполнения O (n), мы заканчиваем только то, что делает O (log n), общее сравнение (по одному на шаг двоичного поиска). Это означает, что если сравнение дорогостоящее, мы можем в конечном итоге выполнять меньшую работу с использованием двоичного поиска, чем выполнять обычный линейный поиск, поскольку O (n) исходит из проделанной работы, идущей по списку, а не из проделанной работы, выполняющей сравнения.