Объектно-ориентированное программирование» для студентов специальности 5В070300 «Информационные системы» идля оп 6В06120 «Информационные системы» Шымкент 2022
жүктеу/скачать 1,44 Mb.
|
ООП ЛЕКЦИОННЫЙ КОМПЛЕКС 2022рус (1)
| Алгоритм бинарного поиска. Алгоритм бинарного поиска требует, чтобы элементы массива поиска были расположены упорядоченно.
Пусть элементы поискового массива расположены в порядке возрастания. Искомый ключ запроса сравнивается со средним элементом массива поиска. Если искомый ключ запроса меньше среднего элемента поискового массива, то все элементы от середины до конца массива в последующем поиске не используются, а все элементы от начала до середины массива подсчитывается массив поиска. Если искомый ключ запроса больше среднего элемента поискового массива, то в последующем поиске не используются все элементы массива от начала до середины, а все элементы от среднего элемента до последнего элемент считается массивом поиска. Таким образом, после операции сравнения половина поискового массива исключается из последующего поиска, поэтому этот алгоритм называется методом половинного расщепления. Далее процесс разбиения повторяется с новым поисковым массивом. Если найден элемент, соответствующий запросу, или массив поиска задан с одним элементом, не соответствующим запросу, то поиск завершается. Преимущество рассматриваемого алгоритма перед другими алгоритмами состоит в том, что время поиска не тратится много. Время поиска пропорционально двоичному логарифму числа элементов поискового массива. Если массив поиска состоит из 1000 элементов, то результат поиска можно получить, используя не более 10 операций сравнения. Если массив поиска состоит из 65 000 элементов, то всего необходимо 16 операций сравнения. Преимущество этого алгоритма особенно заметно при большом количестве элементов поискового массива. Недостатком алгоритма является необходимость настройки массива. Если массив поиска содержит одинаковые элементы, то алгоритм следует «улучшить». Например, названия товаров или фамилии сотрудников. Хэш — это алгоритм поиска, который преобразует ключ в адрес. Лучший способ организовать данные с точки зрения выполнения операций поиска — организовать данные в виде массива, а значение индекса использовать в качестве ключа поиска. В этом случае достаточно один раз обратиться к массиву данных, чтобы найти нужный элемент. Конечно, такие системы редко встречаются в «чистом» виде. Обычно это небольшие системы, например, найти нужную запись можно по номеру ученика или коду учителя. Чтобы найти индекс массива данных, нужно произвести некоторые преобразования по ключам с помощью специальной хеш-функции (HF). Хэш-функция преобразует ключ искомого элемента в числовое значение (индекс) от 0 до n-1. Очевидно, вам нужен массив с N ячейками (хэш-таблица) для хранения значений элементов. Если возможные ключи равны или меньше n, то система преобразуется в адресно-эквивалентную ключевую систему. Если возможные ключи больше n, то следует использовать хеш-функцию. Он обеспечивает равномерное «распределение» ключей между 0 и n-1. Конечно, разным ключам можно присвоить одинаковые индексы, так как хэш-функция работает по принципу «многие к одному». Такая ситуация называется конфликтом. Существуют различные способы организации хеш-функций для ограничения потенциальных конфликтов в заданном значении. При подготовке хэш-функции обычно используется метод деления. Ол бастапқы кезеңде кілтті бүтін санға түрлендіреді, ал одан кейін осы сан 0 мен n-1 аралығына қосылады. жүктеу/скачать 1,44 Mb. Достарыңызбен бөлісу:
|