Пусть массив состоит из N элементов и при поиске разбивается на X равных блоков. Тогда в каждом блоке будет не более N / X элементов. В худшем случае, если искомый элемент окажется в последнем блоке, то для поиска блока потребуется просмотреть X элементов массива. Выполнить линейный поиск в блоке можно, просмотрев не более чем N / X элементов. Следовательно, общее число обрабатываемых элементов не превышает X + N / X. Эта величина зависит от числа блоков и будет минимальна, когда ее производная равна нулю, т.е. при . Число записей в блоке так же равно . При таком разбиении массива на блоки в худшем случае понадобиться обработать не более чем элементов массива, а в среднем — элементов.
К о н т р о ль н ы е в о п р о с ы
1. В чем заключается задача поиска?
2. Всегда ли быстрый линейный поиск быстрее линейного поиска?
3. От чего зависит время поиска в неупорядоченном массиве?
4. Чем алгоритм быстрого линейного поиска в упорядоченном массиве отличается от алгоритма быстрого линейного поиска в неупорядоченном массиве?
|
|
5. В чем заключается бинарный поиск?
6. Определите индексы элементов массива, бинарный поиск которых наиболее продолжителен.
7. Разработайте и реализуйте итеративный и рекурсивный алгоритмы бинарного поиска?
8. В чем заключается блочный поиск?
9. От чего зависит время блочного поиска?
10. Как правильно выбрать количество блоков в блочном поиске?
11. Определите максимальное количество элементов массива, которые могут быть обработаны при блочном поиске.
12. Пусть искомый элемент равен i-му элементу массива. Какой алгоритм рациональнее использовать в этом случае?
13. Выполните сравнительный анализ алгоритмов поиска для случая, когда искомого элемента нет в массиве.
14. Выполните сравнительный анализ алгоритмов поиска для случая, когда в массиве только один элемент.
15. Реализуйте алгоритмы поиска на языке программирования высокого уровня. Выполните трассировку при поиске в массиве из одного элемента.
16. От чего завист порядок функции временной сложности алгоритмов поиска. Каким он может быть для различных алгоритмов?
Л а б о р а т о р н а я р а б о т а № 5