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

Cтраница 1

Линейный поиск ( рис. 4.19) сравнивает каждый элемент массива с ключом поиска. Поскольку массив не упорядочен, вполне вероятно, что отыскиваемое значение окажется первым же элементом массива. Но в среднем, однако, программа должна сравнить с ключей поиска половину элементов массива. [2]

Двоичный поиек. Ключами поиска являются ( а АС, ( b GK. ( c GQ. [3]

Линейный поиск пригоден для коротких таблиц, но для длинных он слишком медлен. На практике невозможно достигнуть оптимального упорядочения в соответствии с частотой. Преимущества простого и быстрого построения таблицы обесцениваются долгим временем поиска. Поэтому для больших таблиц предпочтительны другие способы организации и методы пбиска. В этом методе элементы таблицы сортируются в соответствии с их ключами. Как такая сортировка может быть выполнена, обсуждается в разд. Для настоящего изложения достаточно сказать, что таблица упорядочена. Это означает, что сравнив ключ поиска с ключом любого конкретного элемента, можно определить, равны ли они, или же искомый элемент расположен в таблице ниже или выше этого элемента. После этого только Соответствующая половина таблицы проверяется посредством сравнения ключа поиска с некоторым ключом из этой половины. [4]

Линейный поиск прост и позволяет легко выполнять-добавление новых элементов к существующей таблице, но работает он довольно медленно. Двоичный поиск и его модификации, будучи быстрыми, могут оперировать только с упорядоченными таблицами. Основной недостаток этого метода, делающий его менее полезным для ассемблеров и компиляторов, заключается в том, что добавление новых элементов представляет собой непростой процесс, часто требующий расхода времени на переупорядочение таблицы. [5]

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

Поскольку теперь линейный поиск позволяет найти минимум / по с, производная dJldc равна нулю. [7]

Пример выполнения программы анализа данных опроса ( часть 2 из 2. [8]

Метод линейного поиска хорошо работает для небольших или несортированных массивов. Однако для больших массивов он неэффективен. В случае сортированного массива может быть использован высокоскоростной метод двоичного поиска. [9]

Алгоритм линейного поиска, построенный выше, является только одним из многих возможных методов, но он рассмотрен здесь для иллюстрации используемых принципов. [10]

Метод линейного поиска хорошо работает для небольших или для несортированных массивов. Однако, для больших массивов линейный поиск неэффективен. Если массив отсортирован, можно использовать высокоэффективный метод двоичного поиска. [11]

При линейном поиске ( рис. 6.18) происходит сравнение каждого элемента массива с ключом поиска. Поскольку массив не упорядочен особым образом, вероятность нахождения требуемого значения в первом и в последнем элементах массива одинакова. Таким образом, в среднем программа должна будет сравнить ключ поиска с половиной элементов массива. [12]

При линейном поиске ( последовательном переборе) происходит сравнение каждого элемента массива с ключевым значением. Поскольку массив не упорядочен особым образом, вероятность нахождения требуемого значения в первом и в последнем элементах массива одинакова. Таким образом, в среднем программа должна будет сравнить ключ поиска с половиной элементов массива. Метод последовательного перебора хорошо работает для небольших или несортированных массивов. [13]

При линейном поиске в среднем необходимо просмотреть половину таблицы для нахождения нужного элемента. [14]

Если используется линейный поиск и он запрограммирован, как показано на рис. 3.11, то для каждого цикла поиска будет выполняться пять команд; таким образом, каждая итерация будет выполняться за время около 5 X 12 60 мкс. Число итераций для каждого поиска будет приблизительно равно 1000, половине от общего количества символов в таблице. Наконец потребуется приблизительно один поиск для каждой из 5000 карт. [15]

Страницы: 1 2 3 4