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

Міністерство освіти і науки України

Курсова робота на тему:

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

Зміст

Вступ

Розділ І. Стандартні алгоритми пошуку

1.1 Лінійний пошук

1.2 Алгоритм пошуку діленням пополам (бінарний пошук)

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

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

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

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

2.2 Алгоритм Рабіна-Карпа

2.3 Алгоритм Кнута-Морріса-Пратта

Висновки

Література

Вступ

Задачі, пов'язані із пошуком певного елемента, послідовності елементів у певному масиві, множині або структурі, є досить поширеними і часто використовуваними. Так, у будь якій таблиці, базі даній чи структурі практично завжди присутні методи по пошуку і сортуванню. Кожен, хто виконував різноманітні задачі з допомогою комп'ютера в тому чи іншому випадку обов'язково зустрічався із проблемою пошуку. Якщо ви простий користувач Інтернету, ви обов'язково проводили пошук на пошукових серверах потрібної вам інформації, проводили пошук інформації на окремих сайтах по ключовим словам. Якщо ви працюєте із текстовим редактором MS Word чи Open Office ви обов'язково проводили пошук певних слів у тексті з метою їх редагування чи заміни. Аналогічні дії ви обов'язково проводили і при роботі з іншими програмами будь-то довідник чи окрема база даних. Кожен, хто програмував не зміг би оминути тему "масиви", а отже так чи інакше стикався із необхідністю створення алгоритму пошуку елементів у ньому. Більшість із нас знали, що на різноманітних сайтах, форумах з метою недопущення порушення норм людської поведінки користувачі не мають права вводити образливі слова, заклики до агресії по відношенню до інших і т.п. За це вони можуть бути позбавленні права на певний термін часу відвідувати даний сайт, форум. Зрозуміло, за цим не може слідувати людина, отже існує програма, що зчитує вхідні слова, дані, аналізує їх, проводить пошук і порівняння із забороненими словами у своїй базі і вже відповідно до отриманих результатів проводить певні дії, вимикає, наприклад, доступ до сайту. Ці програми, скрипти, запрограмовані таким чином, щоб проводити як найбільш швидкий пошук. Проте рідко хто задумувався над тим, як же вони працюють і які алгоритми вкладені в пошук.

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

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

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

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

Розділ І. Стандартні алгоритми пошуку

1.1 Лінійний пошук

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

Нехай маємо масив довільного типу: a : array [1..N] of basetype.

Умовою припинення пошуку буде одна із наступних :

) шуканий елемент знайдений в деякій позиції i, тобто a[i]=x ;

) весь масив переглянутий і шуканий елемент відсутній.

Таким чином, алгоритм лінійного пошуку можна записати у вигляді послідовності команд :

i:=1;

while (i<=N) and (a[i]<>x) do i:=i+1;

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

Виникає питання, чи можливо пошук пришвидшити ? Єдиний вихід - спростити умову в заголовку циклу, оскільки вона складається із двох логічних множників. Потрібно сформулювати просту умову, яка буде еквівалентною вихідній. Це можна зробити, якщо гарантувати, що співпадіння з шуканими ключем завжди буде. Тому помістимо вкінець масиву додатковий елемент - "бар'єр" із шуканим значенням 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 );

Readln;

End.

1.2 Алгоритм пошуку діленням пополам (бінарний пошук)

Очевидно, що ніякого іншого способу підвищення ефективності пошуку в масиві не має, якщо відсутня додаткова інформація про дані. Пошук можна значно покращити, якщо елементи в масиві попередньо будуть впорядковані. Даний метод - ділення пополам ще називають "метод дихотомії", "бінарне дерево". Бінарним деревом його називають тому, що можна схематично зообразити дерево, по якому буде проводитися пошук (Рис. 1).

Рис. 1. Дерево порівнянь, що відповідає бінарному пошуку для N=16

Нехай масив a є впорядкованим по зростанню, тобто

, .

Розглядуваний алгоритм базується на таких принципах :

) вибирається довільно деякий елемент, наприклад a m ;

) проводиться порівняння a m з аргументом пошуку x ;

) якщо значення співпадають, то пошук припиняється, якщо a m<x, то відкидаються з розгляду всі елементи масиву до a m включно, якщо a m>x, то відкидаються з розгляду всі елементи масиву після a m включно.

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

Введемо наступні позначення : L, R - індексні змінні, що відмічають відповідно лівий і правий кінці частини масиву, де ще можна знайти потрібний елемент. Алгоритм такого пошуку можна записати у вигляді послідовності команд :

L:=1; R:=N; f:=true;

while (L<=R) and f do

begin

m:=k; {k - довільне значення між L і R}

if a[m]=x then f:=false else

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

end;

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

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

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

if a[m]>x then R:=m-1 else f:=false;

Однак, можна ще покращити ефективність, якщо спростити умову припинення алгоритму. Для цього необхідно відмовитися від бажання припинення пошуку при фіксації співпадання. Тоді пошук продовжуватиметься доти, доки досліджувана частина масиву не стягнеться до одного елемента, який і буде шуканим :

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;

Страницы: 1, 2, 3, 4