Линейный поиск

Простейшей стратегией в этом случае является линейный поиск [5]. Начиная с начала таблицы, последовательно просматривается каждый вход до тех пор, пока не будет найден заданный ключ или же не исчерпается таблица. Легко видеть, что если таблица содержит N входов и если все элементы ее ищутся с равной частотой, то в среднем требуется (N+l)/2&N/2 сравнений для того, чтобы найти заданный ключ. В статической таблице, такой, как таблица кодов машинных операций, которая составляется лишь однажды и затем много раз используется без изменения, можно переупорядочить элементы таким образом, чтобы наиболее часто требующиеся входы расположились ближе к началу, а наименее вероятные входы (такие, как START или STOP) — в самом конце таблицы. Переупорядочение может значительно уменьшить среднюю длину поиска, не влияя на время проверки, и таким образом сократить среднее время поиска.


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Линейный поиск Простейшей стратегией в этом случае является линейный поиск [5]. Начиная с начала таблицы, последовательно просматривается каждый вход до тех пор, пока не будет найден заданный ключ или же не исчерпается таблица. Легко видеть, что если таблица содержит N входов и если все элементы ее ищутся с равной частотой, то в среднем требуется (N+l)/2&N/2 сравнений для того, чтобы найти заданный ключ. В статической таблице, такой, как таблица кодов машинных операций, которая составляется лишь однажды и затем много раз используется без изменения, можно переупорядочить элементы таким образом, чтобы наиболее часто требующиеся входы расположились ближе к началу, а наименее вероятные входы (такие, как START или STOP) — в самом конце таблицы. Переупорядочение может значительно уменьшить среднюю длину поиска, не влияя на время проверки, и таким образом сократить среднее время поиска.