Линейный поиск Sentinel лучше, чем обычный линейный поиск?
Что такое линейный поиск Sentinel?
Sentinel Linear search is a type of linear search where the element to be searched is placed in the last position and then all the indices are checked for the presence of the element without checking for the index out of bound case.
Количество сравнений в этом поиске уменьшено по сравнению с традиционным линейным поиском. Когда линейный поиск выполняется в массиве размера N , то в худшем случае выполняется всего N сравнений, когда искомый элемент сравнивается со всеми элементами массива, и выполняется (N + 1) сравнений для индекс сравниваемого элемента, чтобы индекс не выходил за пределы массива, который можно уменьшить в линейном поиске Sentinel. Таким образом, всего сравнений в худшем случае может быть 2*N + 1 .
Но в этом поиске последний элемент массива заменяется искомым элементом, а затем линейный поиск выполняется в массиве без проверки того, находится ли текущий индекс в диапазоне индексов массива или нет, потому что элемент, который нужно найти, искомый обязательно будет найден внутри массива, даже если его не было в исходном массиве. Таким образом, проверяемый индекс никогда не выйдет за пределы массива. Количество сравнений в худшем случае будет (N+2) .
Реализации:
См. ниже реализации обоих алгоритмов поиска:
Реализация линейного поиска:
Временная сложность : O(N)
Вспомогательное пространство : O(1)
Реализация линейного поиска Sentinel:
Ниже приведены шаги для реализации алгоритма:
- В дозорном поиске мы сначала вставляем целевой элемент в конец списка, а после этого сравниваем каждый элемент списка, пока не найдем нужный нам элемент.
- Либо нужный элемент есть в списке, в этом случае он будет найден до того, как мы дойдем до конца списка.
- Или в списке не было целевого элемента, поэтому алгоритм дойдет до конца списка и найдет целевой элемент, который мы вставили изначально.
- Здесь нам нужно сделать только одно сравнение, нам нужно только проверить, соответствует ли элемент целевому элементу или нет, и нам не нужно проверять, выходим ли мы из списка.
- Наконец, проверьте, был ли найденный нами элемент уже в списке или был добавлен нами в конец списка.
- Эта проверка произойдет только один раз после окончания цикла.
Ниже приведен код для реализации шагов.
Временная сложность : O(N)
Вспомогательное пространство : O(1)
Вывод:
В Sentinel Linear Search мы делаем на одно сравнение меньше на каждом шаге. Таким образом, временная сложность значительно сокращается. Как упоминалось ранее, мы видим, что в худшем случае традиционный линейный поиск использует 2*N+1 сравнений, тогда как линейный поиск Sentinel выполняет только N+2 сравнений.
So we can conclude that Sentinel Linear Search is better than normal Linear Search.