AOP_Tom3 (1021738), страница 115
Текст из файла (страница 115)
! На рис. 6 показано бинарное дерево, соответствующее поиску при Ю = 10. В случае неудачного поиска алгоритм может выполнить излишнее сравнение непосредственно перед окончанием работы; такие узлы иа рисунке заштрихованы. Мы называем этот процесс поиска одноробным потому, что разность между числами узла на уровне 1 и его узла-предшественника на уровне 1 — 1 представляет собой константу б для всех узлов на уровне Е Теория, лежащая в основе алгоритма (), может быть пояснена следующим образом, Предположим, что у иас имеется интервал для поиска длиной и — 1; сравнение со средним элементом (для четного и) или с одним из средних элементов (для нечетного и) дает нам два интервала — длиной (и/2) — 1 и (п/21 — 1.
После повторения этого процесса к рэз мы получим 2ь интервалов, наименьший из которых имеет длину (и/2ь) — 1, а наибольший — (и/2ь) — 1. Следовательно, длина двух интервалов иа одном уровне отличается ие более чем иа единицу; это делает возможным выбор "среднего" элемента без запоминания точных значений длин интервалов. РИС. В.
Дврвао СраВНЕНИй дпя ьодиереднОГОь бИНарНОГО ПОИСКа Прн Х = 10. Принципиапьное достоинство алгоритма [1 заключается в том, что нам совершенно не нужно хранить значение гп; необходима только ссылка на небольшую таблицу б для использования на каждом уровне дерева. Таким образом, алгоритм сводится к следующей процедуре, одинаково подходящей как для бинарных, так и для десятичных компьютеров. Алгоритм С (Однородный бинарный поиск). Этот алгоритм подобен алгоритму 1], но использует вспомогательную таблицу вместо вычислений; ~дг+21 ') РЕ[.ТА[Я = ~ . 1 для 1 < 0 ( [18Х] + 2. 21 [б) В упр.
8 доказывается, что настоящий алгоритм использует искусственный ключ Ке = -со только при четных лг. Программа С (Одкародкмй бинарный поиск). Эта программа выполняет ту же задачу, что и программа В, используя алгоритм С; при этом гА = К, г11 ш 1, г]2 = з', г[3 ьн РЕ1 ТА [1]. 01 ЯТАНТ ЕМТ1 М+1/2 а и~ь„ьд~ ' С#+1)/ц. 03 ЕМТ2 2 1,~' +- 2. 00 1РА К 1 04 ЮМР 2Р 1 05 ЗН дЕ ЯРССЕЯЯ С1 Переход, если К = Ке 00 132 РА11РНЕ С1 — Я Переход, если 031ТА[]] = О.
07 РЕС1 0,3 С1 — 5 — А СЗ. Уменьшение 1. 00 ЯН 1НС2 1 С вЂ” 1 д <-,у+1, С1. [Инициализация.] Установить 1 < — РЕ1.ТА [1], З' < — 2. С2. [Сравнение.) Если К < Кп перейти к шагу СЗ; если К > К„перейти к шагу С4; если К = К;. алгоритм успешно завершается. СЗ. [Уменьшение Ц Если БЕ|ТА Ц] = О, алгоритм завершается неудачно. В противном слу чае установиты ь — 1 — РЕ1ТА [1'], З с — 0 + 1 и перейти к шагу С2.
С4. [Увеличение 1.) Если РЕ1.ТА[1] = О, алгоритм завершается неудачно. В противном случае установнты < — 1+ РЕ|ТАЦ], 1 <- 1'+ 1 и перейти к шагу С2. 1 Рис. 7. Дерево сравнений для почти равномерного поиска по методу Шара при 1ч' = 10. с с.с С С С2 С2 1 — 3 00 2Н ЬВ3 ВЕЬТА, 2 10 СМРА КЕ7,1 11 ЗЬЕ ЗВ 10 1ИС1 О,З 1Я 1ЗМЕ ЕВ Ц РА1ЬОНЕ ЕЦО Переход, если К < К,. С4, Увеличение Ь Переход, если ВЕЬТА 1Я ф О. Выход при отсутствии в таблице. В случае успешного завершения поиска данный алгоритм соответствует бинарному дереву с такой же длиной внутреннего пути, как и в алгоритме В, позтому среднее количество сравнений Сн остается прежним, При неудачном поиске алгоритм С всегда выполняет в точности (!8 Л) + 1 сравнений.
Общее время работы программы С не совсем симметрично по отношению к левым и правым ветвям, и С1 имеет больший вес, чем С2. Впрочем, в упр. 11 будет показано, что случаи К < К, имеют ту же вероятность, что и К > Кь Следовательно, программа С работает приблизительно следующее время: (8.5 !8 1У вЂ” 6) и при успешном поиске, (85(!ЕЖ!+12)и при неудачном поиске.
(7) Другая модификация бинарного поиска, предложенная в 1971 году ЗЬ Э. Шаром (Ь. Е. ЕЛаг), на некоторьгх компьютерах будет работать еще быстрее, так как она однородна после первого шага и не требует использования таблицы. Первый шаг состоит в сравнении К и К,, где ! = 2ь, А = (!8!ч'1, Если К < К,, мы используем однородный поиск с 6 = 2ь ', 2А ', ..., 1, О. С другой стороны, если К > К„мы устанавливаем 1 = Р = Ж + 1 — 2', где ! = ! !8(М вЂ” 2ь + 1)~, и, делая вид, что первое сравнение на самом деле было К > К,, используем бинарный поиск с Б = 2' ', 2' з, ..., 1, О. Метод Шара для Х = 10 проиллюстрирован на рис. 7.
Подобно предыдущим алгоритмам, он никогда не выполняет больше (!8 Х) + 1 сравнений. Следовательно, выполняемое им количество сравнений превышает минимально возможное среднее значение не более чем на единицу — несмотря на то, что иногда алгоритму Это более чем в два раза быстрее программы В; при этом специфика бинарного ком- пьютера не используется (в случае времени работы (5) программы В предполагалось наличие команды битового сдвига в компьютере М1Х). приходится проводить несколько избыточных сравнений прн успешном поиске (см. упр. 12). Еще один вариант бинарного поиска, который осуществляется быстрее всех описпнных прн очень больших Ж, обсуждается в упр.
23. Но в упр. 24 вы найдете еще более быстрый метод... *Поиск Фибоначчи. Прн рассмотрении многофвзного слияния мы видели, что числа Фнбоначчн могут играть такую же роль, что и степени числа 2. Подобное явление наблюдается н прн поиске, где числа Фнбоначчн позволяют разработать альтернативу бинарному поиску. Для некоторых компьютеров предлагаемый метод предпочтителен в связи с тем, что в нем используются только сложение н вычитание (без деления на 2). Следует различать процедуру, которую мы начинаем обсуждать, н важный численный метод, также называемый японском Фнбоначчн", используемый для поиска максимума уннмодвльной функции [см.
Е!Ьопасс! Яиагсег!у 4 (1966), 265 — 269). Совпадение названий* нередко приводит к недоразумениям! Технология поиска Фнбоначчи, на первый взгляд, представляется весьма загадочной, н, если просто взять программу н постараться понятвп как она работает, вам покажется, что это полное шаманство. Однако шаманство превратится в обычный танец с бубном, как только мы построим соответствующее дерево поиска.
Поэтому наш рассказ начнется с деревьев Фибоначчи. На рнс. 8 показано дерево Фнбоначчн порядка 6. Оно больше похоже на реальный, не очень хорошо подстриженный куст, чем на другие деревья, которые мы рассматривали. Возможно, это связано с тем, что многие природные процессы опнсываются законом Фнбоначчн. В целом, дерево Фнбоначчн порядка к имеет Гя+г — 1 внутренних (на рисунке — круглых) н Ейег внешних (на рисунке квадратных) узлов. Строится оно следующим образом. Если к = 0 илн Ь = 1, дерево вырождается в ДЮ.
Если й > 2, корнем является Р~; левое поддерево представляет собой дерево Фнбоначчн порядка Ь вЂ” 1; правое поддерево представляет собой дерево Фнбоначчн порядка !с — 2 с числами, увеличенными на Еа. Обратите внимание на то, что, за исключением внешних узлов, числа двух дочерних узлов каждого внутреннего узла отличаются от него на одну н ту же величину, н эта величина — не что иное, как число Фнбоначчн (напрнмер, на рассматриваемом рисунке 5 = 8 — Гя н 11 = 8 + Ра).
Если разница на каком-лнбо уровне составляет Е'., то на следующем уровне она будет равна Р' г для левой ветви н Е! я — для правой. Так, например, 3 = 5 — Рэ, а 10 = 11 — Гэ. Комбинируя этн наблюдения с механизмом распознавания внешних узлов, мы получим следующий алгоритм поиска. Алгоритм Р (11оиск Фибонпччи (Ргбопвссяпп ясвгс!г)). Дана таблица записей Вэ Вэ ...Лдг, ключи которых расположены в порядке возрастания Кг < Кэ « .
Кас Алгоритм осуществляет поиск заданного аргумента К. * Нужно отметить, что в английском яэыке такое совпадение превращается в обычную схожесть; метод поиска, который мы будем рассматривать, именуется "Р!Ъопассгап яеагсь", а метод поиска максимулга унимодальной функции — хт ~Ьопасс1 яеагсь" — Прям. нерее. Рис. 8. Дерево Фибоначчи порядка б. Для удобства описания предполагается, что Гу + 1 представляет собой число Фибоначчи Ге+1 (выполнив соответствуюшую инициализацию, алгоритм несложно распространить на любые значения Аг; см. упр, 14). Е1.
(Инициализация.) Установить 1 е — Гы р с — Гы ы О +- Гь с. (В описании этого алгоритма р и д означают последовательные числа Фибоначчи.) Г2. 1Сравнение.] Если К < К„перейти к шагу ГЗ; если К > Кп перейти к шагу Е4; если К = К„алгоритм успешно завершается. ЕЗ. [Уменьшение г'.] Если 0 = О, алгоритм завершается неудачно. В противном случае следует установиты +- 1 — 0 и (р, 0) с — (д, р — д); затем перейти к шагу Е2. Е4. (Увеличение Ц Если р = 1, алгоритм завершается неудачно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
