Сравнение двоичного и линейного способов поиска

Поскольку фактически интересующая нас таблица делится пополам при каждой пробе, максимальное число проб, необходимое для поиска в таблице, состоящей из N элементов, близко к log N. Так как вероятность обнаружения точного совпадения на ранних сравнениях много меньше вероятности выявления неравенства, выражение log N дает также и хорошую аппроксимацию SL. На рис. 5.8 показана средняя длина поиска для линейного и двоичного способов поиска. Из графика видно, что применение двоичного поиска требует меньшего числа сравнений, чем при линейном поиске.

Однако нельзя сравнивать эти два метода так прямолинейно. Прежде всего необходимой предпосылкой двоичного поиска является упорядоченность таблицы. Сортировка элементов таблицы дополнительного времени. Если таблица, используется в основном для поиска и лишь изредка пополняется новыми элементами, этим временем можно пренебречь. С другой стороны, времена проверки значительно отличаются, т. е. TCi двоичное, линейное из-за более сложного алгоритма выбора элемента для сравнения ключа. Для ЭВМ типа IBM 360/40 эти времена относятся приблизительно как 5:1. Таким образом, для небольших N линейный поиск более эффективен, чем двоичный. Переходная точка расположена обычно около N 50—100 элементов для машин типа IBM 360. Приблизительная иллюстрация этого факта приведена на рис. 5.9.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Сравнение двоичного и линейного способов поиска Поскольку фактически интересующая нас таблица делится пополам при каждой пробе, максимальное число проб, необходимое для поиска в таблице, состоящей из N элементов, близко к log N. Так как вероятность обнаружения точного совпадения на ранних сравнениях много меньше вероятности выявления неравенства, выражение log N дает также и хорошую аппроксимацию SL. На рис. 5.8 показана средняя длина поиска для линейного и двоичного способов поиска. Из графика видно, что применение двоичного поиска требует меньшего числа сравнений, чем при линейном поиске. Однако нельзя сравнивать эти два метода так прямолинейно. Прежде всего необходимой предпосылкой двоичного поиска является упорядоченность таблицы. Сортировка элементов таблицы дополнительного времени. Если таблица, используется в основном для поиска и лишь изредка пополняется новыми элементами, этим временем можно пренебречь. С другой стороны, времена проверки значительно отличаются, т. е. TCi двоичное, линейное из-за более сложного алгоритма выбора элемента для сравнения ключа. Для ЭВМ типа IBM 360/40 эти времена относятся приблизительно как 5:1. Таким образом, для небольших N линейный поиск более эффективен, чем двоичный. Переходная точка расположена обычно около N 50—100 элементов для машин типа IBM 360. Приблизительная иллюстрация этого факта приведена на рис. 5.9.