Алгоритмы и структуры данных

Sentinel Linear Search

Представляет собой тип линейного поиска, в котором количество сравнений уменьшено по сравнению с традиционным линейным поиском.

Основная идея заключается в добавлении дополнительного элемента в конец массива (т. е. значения дозорного), который соответствует ключу поиска.

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

Сложность: O(n)

www.tgoop.com/the_algorithms/4581

6.5K viewsOct 23, 2023 at 09:02

Sentinel Linear Search

Представляет собой тип линейного поиска, в котором количество сравнений уменьшено по сравнению с традиционным линейным поиском.

Основная идея заключается в добавлении дополнительного элемента в конец массива (т. е. значения дозорного), который соответствует ключу поиска.

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

Сложность: O(n)

BY Алгоритмы и структуры данных