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

Виникає питання, чи можливо пошук пришвидшити ? Єдиний вихід - спростити умову в заголовку циклу, оскільки вона складається із двох логічних множників. Потрібно сформулювати просту умову, яка буде еквівалентною вихідній. Це можна зробити, якщо гарантувати, що співпадіння з шуканими ключем завжди буде. Тому помістимо вкінець масиву додатковий елемент - "бар’єр" із шуканим значенням x . Звичайно, при цьому необхідно попередньо розширити на один елемент масив a та діапазон допустимих значень індекса :

a : array [1..N+1] of basetype.

Алгоритм в цьому випадку матиме вигляд :

i:=1; a[N+1]:=x;

while a[i]<>x do i:=i+1;

В обох випадках алгоритму істинність умови i=N+1 свідчить про відсутність шуканого елемента в масиві.

Аналіз лінійного пошуку. Очевидним є той факт, що кількість основних операцій порівняння, необхідних для встановлення входження шуканого елемента, залежить від його позиції і взагалі від його наявності в масиві. Оскільки тип масиву basetype може бути досить складним і великим по об’єму пам’яті, то можна вважати порівняння елементів цього типу складнішою операцією ніж порівняння індексів. Спочатку оцінимо кількість порівняння ключів. Зрозуміло, що для обох алгоритмів вона буде однаковою. В найкращому випадку, коли потрібний елемент знаходиться на першому місці, виконається лише одна операція. В найгіршому випадку, коли шуканого елемента не має, виконається N операцій. Середня ж кількість порівнянь - N/2 . Якщо враховувати і порівняння індексів для встановлення кінця масиву, то початковий варіант алгоритму потребуватиме додатково ще таку ж саму кількість.

Реалізація алгоритму на Turbo Pascal. Нехай маємо масив із N символів, необхідно знайти елемент K і вивести якщо він є в масиві його індекс.

Program Seach_1_1;

Uses Crt;

Const n=10;

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

i, k:integer;

Begin

ClrScr;

Randomize;

For i:= 1 to n do

Begin

A[i]:=Random(10);

Write(A[i]:3);

End;

Writeln;

Writeln(‘Vvedit k’);

Readln(k);

A[0]:=k;

I:=n;

While a[i]<>k do

Dec(i);

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