Skip to content

Master's | Basic Algorithms & Data structures | Module 5 | Searching Algorithms

Notifications You must be signed in to change notification settings

LesiaUKR/goit-algo-hw-05

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

goit-algo-hw-05

Home work | Module 5 | Searching algorithms

Task 3

Підрядок Алгоритм Стаття 1 (сек) Стаття 2 (сек)
алгоритмів Boyer-Moore 0.013954 0.154882
алгоритмів KMP 0.025298 0.402018
алгоритмів Rabin-Karp 0.064253 0.904445
неіснуючий підрядок для тестування Boyer-Moore 0.223007 0.348797
неіснуючий підрядок для тестування KMP 1.36795 2.00499
неіснуючий підрядок для тестування Rabin-Karp 3.40861 5.62853

Результати тестів швидкодії різних алгоритмів пошуку рядку показують наступні висновки:

Boyer-Moore:

  • Цей алгоритм виявився найшвидшим для пошуку підрядка "алгоритмів" у обох статтях. Його час виконання у Статті 1 становить 0.013954 секунд, а у Статті 2 — 0.154882 секунд.
  • Для підрядка "неіснуючий підрядок для тестування" Boyer-Moore також був найшвидшим, але час виконання значно зріс до 0.223007 секунд у Статті 1 і 0.348797 секунд у Статті 2. Це пояснюється тим, що Boyer-Moore краще працює з короткими підрядками.

KMP (Knuth-Morris-Pratt):

  • Цей алгоритм був повільнішим за Boyer-Moore у всіх тестах, але швидшим за Rabin-Karp для підрядка "алгоритмів". У Статті 1 його час виконання становить 0.025298 секунд, а у Статті 2 — 0.402018 секунд.
  • Для підрядка "неіснуючий підрядок для тестування" KMP був повільнішим: 1.36795 секунд у Статті 1 і 2.00499 секунд у Статті 2. Це свідчить про те, що KMP може бути менш ефективним для довгих підрядків.

Rabin-Karp:

  • Цей алгоритм показав найгірші результати у всіх тестах. Для підрядка "алгоритмів" його час виконання становив 0.064253 секунд у Статті 1 і 0.904445 секунд у Статті 2.
  • Для підрядка "неіснуючий підрядок для тестування" час виконання був значно більшим: 3.40861 секунд у Статті 1 і 5.62853 секунд у Статті 2. Це показує, що Rabin-Karp є менш ефективним для довгих підрядків і для великих текстів.

Висновки:

Boyer-Moore є найефективнішим алгоритмом для пошуку коротких і довгих підрядків у великих текстах. Він має найменші часи виконання у всіх тестах.

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

Rabin-Karp є найменш ефективним алгоритмом у даних тестах. Його час виконання значно перевищує Boyer-Moore і KMP у всіх випадках.