Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах (стр. 2 из 4)

L:=1; R:=N;

while L<R do

begin

m:=(L+R) div 2;

if a[m]<x then L:=m+1 else R:=m

end;

Умова припинення циклу L>=R досягається. Адже для цілочисельного серединного значення m справедлива нерівність L<=m<R, якщо попередньо виконувалася умова L<R. Отже, або L збільшується при присвоєнні йому значення m+1, або R зменшується при присвоєнні йому значення m. Таким чином, різниця R-L на кожному кроці зменшується, і при досягненні нульового значення (L=R) повторення циклу припиняється.

Варто зауважити, що виконання умови L=R ще не гарантує знаходження потрібного ключа. Потрібно враховувати, що елемент a[R] в порівнянні ніколи участі не бере. Тому необхідна додаткова перевірка після циклу на рівність a[R]=x.

Розглянутий алгоритм як і алгоритм лінійного пошуку знаходить шуканий елемент з найменшим індексом, тобто перше входження в масив. А простий бінарний пошук - довільний із співпадаючих елементів.

Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив елементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи бінарний пошук.

Program Seach_1_2;

Uses Crt;

Const n=10;

Var a:array [1..n] of integer;

i, k,l,r:integer;

Begin

ClrScr;

For i:=1 to n do

Readln(A[i]);

Writeln(‘Vvedit k’);

Readln(k);

l:=1; r:=n;

while l<r do

begin

i:=(l+r) div 2;

if a[i]<k then l:=i+1

else r:=i

end;

Writeln(‘element ’,k,’ mae index ‘,i+1 );

Readln;

End.

1.3 Пошук по "дереву Фібоначе".

Існує ще один метод подібний до методу описаного вище, проте ефективність його дещо вища ніж пошуку по бінарному дереву, хоча така ж пропорціональність log(2)N. В дереві Фібоначе числа в дочірніх вузлах відрізняються від батьківських на одну і ту ж величину, а саме на число Фібоначе (рис. 2.).

Суть даного метода в тому, що порівнюючи наше шукане значення з наступним значенням в масиві, ми не ділимо навпіл нову зону пошуку, як в бінарному пошуку, а відступаємо від попереднього значення, з яким порівнювали, в потрібну сторону на число Фібоначе.

Рис. 2. Дерево Фібоначе порядку 6

Ефективність даного метода вища за ефективність методу бінарного дерева в тому, що метод Фібоначе включає в себе тільки такі арифметичні операції, як додавання і віднімання, немає необхідності в діленні на 2, тим самим економиться процесорний час. Адже, як відомо виконання операцій віднімання і додавання проходить на порядок швидше ніж операція множення чи ділення.

Даний метод був винайдений в 60-ті роки.

Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив Nелементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи метод Фібоначе.

Program Seach_1_3;

Uses Crt;

Var a:array [1..200] of integer;

i,n,k,j,l,x,y,z,tmp,q,p:integer;

Begin

ClrScr;

Write('Vvedit kilkist chleniv poslidovnocti');

readln(n);

for j:=1 to 3 do

begin

l:=1;x:=1;y:=0;

While l<trunc(n/2)+1-j do

begin

z:=x; l:=l+1;

x:=x+y; y:=z;

end;

Case j of

1:i:=x;

2:p:=x;

3:q:=3;

end;

end;

Writeln('-----------------------------');

For i:=1 to n do

Readln(A[i]);

Writeln('-----------------------------');

Writeln('Vvedit k');

Readln(k);

while a[i]<>k do

begin

if k<a[i] then begin i:=i-q; tmp:=q; q:=p-q;p:=tmp;end

else begin i:=i+q; p:=p-q; q:=q-p; end;

end;

Writeln('element ',k,' mae index ',i);

Readln;

End.

1.4 Метод екстраполяції

Даний метод в деякій мірі подібний до "методу дихотомії", наведеного вище. Проте, щоб краще зрозуміти даний метод, давайте представимо собі, що нам потрібно взнати, як перекладається на українську мову англійське слово treasure. Тобто в нас задача – знайти це слово в словнику.

По суті, всі наші дії будуть нічим іншим, як реалізацією деякого алгоритму пошуку. Масив значень – це словник, всі значення в ньому відсортовані за алфавітом. Шукане слово нам відомо. Тобто будемо проводити пошук в відсортованому масиві. З першого погляду стає зрозумілим, що ми не будемо перебирати всі слова словника, як і не будем ділити книгу навпіл, дивитися що там в середині і відраховувати в одну і другу сторону рівно ¼ сторінок словника і т.д. (за умови що словник великий). Тобто метод дихотомії і лінійний пошук буде проігноровано.

Більш ніж вірно що ми спочатку відкриємо словник дещо дальше ніж на середині (літера t за серединою латинського алфавіту). Якщо відкрили на літері R, ясно, що шукати потрібно в другій частині словника, а на скільки відступити? На половину? "Навіщо ж на половину, це більше, чим потрібно", скажете ви і будете праві. Адже нам не просто відомо, в якій частині масиву шукане значення, ми володіємо ще і інформацією про те наскільки далеко потрібно зробити наступний крок!

Ось ми і підійшли до суті розглядуваного методу. На відміну від перших двох методів, він не лише визначає зону нового пошуку, а і оцінює величину кроку. Алгоритм називається екстраполяційний метод і має швидкість сходження більшу, ніж метод поділу навпіл.

Якщо при пошуку по бінарному дереву за кожний крок масиву пошуку зменшується з N до значення N/2, то при цьому методі за кожен крок зона зменшується з N значення до кореня квадратного з N. Якщо K лежить в межах Kn і Km, то наступний крок робимо від n на величину (n - m)*(K - Kn)/(Km - Kn). Швидкість екстраполяційного методу розпочинає суттєво перевершувати швидкість метода половинного ділення при великих значеннях.

Реалізація алгоритму на Turbo Pascal. Нехай дано впорядкований масив Nелементів цілочисельного типу, знайти заданий елемент і вивести його позицію у масиві використовуючи екстраполяційний метод.

Program Seach_1_4;

Uses Crt;

Var a:array [1..200] of integer;

i,j,n,k,l,r:integer;

Begin

ClrScr;

Write('Vvedit kilkist chleniv poslidovnocti = ');

readln(n);

Writeln('-----------------------------');

For i:=1 to n do Readln(A[i]);

Writeln('-----------------------------');

Writeln('Vvedit k');

Readln(k);

l:=1; r:=n; i:=1;

while r>l do

begin

i:=(((r-l)*(K-a[l])) div (a[r]-a[l]));

if (K<a[i])then r:=i-1

else l:=i+1;

if K=a[i] then Writeln('element ',k,' mae index ',l);

end;

readln;

End.

Розділ ІІ. Пошук підрядка в рядку

2.1 Прямий пошук підрядка

Часто доводиться зустрічатися із специфічним пошуком - так званим пошуком рядка. Мається на увазі визначення позиції в одній послідовності елементів, починаючи з якої інша послідовність повністю в неї входить. Така операція часто зустрічається в задачах обробки текстів.

Нехай задано масив a із N елементів та масив b із M елементів, які називаються відповідно базовим рядком та підрядком або образом, причому

:

a : array [1..N] of basetype ; b : array [1..M] of basetype ;

Пошук рядка передбачає встановлення першого входження образа b в базовий рядок a.

Прямий пошук полягає в повторюваному порівнянні елементів двох масивів. У випадку неспівпадання чергової пари елементів образ зсувається на одну позицію вздовж базового масиву і процес порівняння проводиться знову починаючи з першого елемента шуканого підрядка.

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

x y z t u x y t

x y t

Процес порівняння елементів може припинитися при виконанні однієї із двох умов :

всі елементи образа співпали з відповідними елементами бази - це означає, що позиція входження встановлена ;

після чергового неспівпадання елементів та зсуву образа відбувся вихід підрядка за межі бази - це означає, що шуканий підрядок не входить в базовий.

Якщо позначити біжучий індекс по базі через i , а індекс по образу через j , то ці умови можна записати у вигляді диз’юнкції логічних виразів (j>M) or (i>N-M+1) .

Таким чином програмна реалізація прямого пошуку підрядка в рядку матиме вигляд процедури :

Var

i, j, k : integer;

Begin

i:=1; j:=1; k:=0;

while (j<=M) and (i<=N-M+1) do

begin

j:=k+1; k:=j; i:=1;

while a[j]=b[i] do

begin inc(v); i:=i+1; j:=j+1; end;

end;

if i>m then writeln('номер позиції входження ',(j+1)-i,' важких операцій виконується N=',v+w )

else writeln('не має входження образу в базу, важких операцій виконується N=',v+w);

readln;

END.

Просто і елегантно, вроді би так і потрібно. Дійсно, це не важко у виконанні, але і не дуже ефективно на практиці. Давайте проведемо оцінку швидкості роботи цього алгоритму. В ньому присутні два цикли (один вкладений), час роботи зовнішнього циклу більшою мірою залежить від n, а внутрішній в гіршому випадку дає m операцій. Таким чином, час роботи всього алгоритму рівний O((n-m+1)m). Для малих рядків пошук пройде досить швидко, але якщо в деякому багатомегабайтному файлі буде потрібно знайти послідовність довжиною 100 Кб, то час затрачений на пошук буде дуже великий.Основним недоліком даного методу є те, що приходиться виконувати багато "лишньої" роботи. Наприклад, знайшовши рядок aabc і виявивши невідповідність в четвертому символі (співпало тільки aab), алгоритм буде продовжувати порівнювати рядок, починаючи із наступного символу, хоча це однозначно не приведе до вірного результату. Даний алгоритм найбільш придатний до невеликого об’єму тексту.