1.1. Лінійний пошук
Читачеві колись доводилося шукати своє прізвище в списках, надрукованих не в алфавітному порядку? Або уявіть собі словник на 100 тисяч слів, розташованих там без упорядкування за алфавітом. Потрібне слово шукати там доведеться довго. Дуже довго. Звичайно, якщо воно випадково не потрапило в самісінький початок. А якщо в кінець чи середину? А пошук слова в "нормальному" словнику займає чомусь кілька секунд незалежно від його розташування там.
У цьому параграфі ми наведемо два алгоритми. Перший описує пошук "підряд" у невпорядкованій послідовності, другий – той пошук, до якого ми звикли, шукаючи слова в словниках. Замість слів розглянемо цілі значення елементів масиву. Тип значень може бути й іншим – головне, щоб їх можна було порівнювати.
Нехай елементи масиву A [1], A [2], … , A [n ] та змінна key ("ключ") мають той самий тип T. Пошук за ключем полягає в пошуку номера i такого, що A [i ]= key . За відсутності такого номера результатом будемо вважати 0. Нехай діють означення
const maxn = 1000;
Возможно вы искали - Реферат: Конкуренція 4
type T = integer;
Indx = 1 .. maxn; (17.1)
ArT = array [Indx] of T;
Подамо розв'язання задачі функцією
function srcseq ( var A : ArT; n : Indx; key : T) : integer;
Похожий материал - Дипломная работа: Экономика и управление производством на железной дороге
var i : integer;
begin
i := 0;
while ( i <= n ) do
if A[i]<> key then i := i + 1 else break ;
Очень интересно - Реферат: Организация экскурсионного обслуживания в гостиничных и туристических комплексах
{ i = n + 1 або A[i] = key }
if i < n + 1 then srcseq := i
else srcseq := 0
end
З'ясуємо, яким чином час пошуку за цим алгоритмом залежить від кількості n елементів масиву. Узагальнимо присвоювання та операції над значеннями скалярних типів (порівняння, додавання, множення тощо) терміном елементарна дія . Будемо вважати, що на виконання кожної елементарної дії витрачається скінченний обмежений проміжок часу, незалежний від конкретних операндів . За такого припущення час виконання програми (підпрограми) прямо пропорційний кількості елементарних дій у процесі виконання.
Вам будет интересно - Реферат: Казахские традиции 2
Очевидно, що кількість елементарних дій при виконанні функції srcseq прямо пропорційна кількості порівнянь A[i]<>key. В найгіршому випадку з ключем порівнюються всі елементи масиву. Звідси максимальна кількість дій та найбільший час виконання функції прямо (лінійно) пропорційні n , і найбільший час пошуку t 1 є лінійною функцією від кількості елементів масиву. Описаний спосіб пошуку називається лінійним . Лінійну залежність часу від кількості елементів, тобто довжини n , будемо позначати символом "O": t 1 = O(n ).
1.2. Дихотомічний пошук
Тепер опишемо так званий дихотомічний пошук у "нормальному словнику". Ми розкриваємо словник приблизно в його середині. Якщо слово повинно бути в словнику далі, то шукати треба лише в другій половині словника. Його середина стає для нас початком, і ми розкриваємо його на середині другої половини. Аналогічно, коли слово повинно бути в першій половині, ми залишаємо для пошуків лише її. Отже, кожне заглядання в словник поділяє "простір пошуку" на дві половини й зменшує його приблизно вдвічі. Звідси й назва, оскільки дихотомія – це поділ на дві половини. Такий пошук ще називають двійковим , або бінарним .
Нехай значення елементів масиву упорядковані за зростанням, тобто A [1]£ A [2]£ … £ A [n ] (кажуть, масив відсортований ). Опишемо дихотомічний пошук такою функцією:
function srcbin ( var A : ArT; n : Indx; key : T) : integer;
Похожий материал - Реферат: Понятие о хозяйственных операциях и их виды
var i, hb, lb : integer;
begin
lb := 1; hb := n;
i := (lb + hb) div 2;