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

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

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

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

Зміст

Вступ

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

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.

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