Курсовая работа: Порівняльний аналіз ефективності та складності алгоритмів пошуку елементів у масивах

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

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

Якщо позначити біжучий індекс по базі через 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 ), алгоритм буде продовжувати порівнювати рядок, починаючи із наступного символу, хоча це однозначно не приведе до вірного результату. Даний алгоритм найбільш придатний до невеликого об’єму тексту.

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

Program Seach_2_1;

Uses Crt;

Const nmax=10000;

var p:string; {підрядок}

s:array[1..nmax]of char; {рядок}

d:array[char]of byte; {масив зрушень}

c:char;

m,i,j,k:integer;

begin