CarpathianUA/goit-algo-hw-05

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

Цей документ містить результати порівняльного аналізу трьох алгоритмів пошуку - Boyer-Moore, Knuth-Morris-Pratt (KMP) та Rabin-Karp - на основі часу їх виконання, здатності знаходити задані рядки у текстах та їхньої складності за Big-O нотацією.

Результати

Нижче представлені таблиці з часом виконання кожного алгоритму для двох різних текстів і шаблонів, а також їхньою теоретичною складністю. Використано два шаблони для порівняння - перший шаблон міститься в тексті data/article_1.txt і другий шаблон міститься в тексті data/article_2.txt.

Текст: data/article_1.txt

Шаблон	Алгоритм	Big-O Нотація	Час (секунди)	Результат
Фундаментальні знання допомагають дізнатися	Boyer-Moore	O(n)	0.000043	Так
Фундаментальні знання допомагають дізнатися	KMP	O(n + m)	0.000165	Так
Фундаментальні знання допомагають дізнатися	Rabin-Karp	O(n + m) у середньому, O(nm) у гіршому випадку	0.000297	Так
Вибір методу представлення даних	Boyer-Moore	O(n)	0.000253	Ні
Вибір методу представлення даних	KMP	O(n + m)	0.001205	Ні
Вибір методу представлення даних	Rabin-Karp	O(n + m) у середньому, O(nm) у гіршому випадку	0.001988	Ні

Текст: data/article_2.txt

Шаблон	Алгоритм	Big-O Нотація	Час (секунди)	Результат
Фундаментальні знання допомагають дізнатися	Boyer-Moore	O(n)	0.000326	Ні
Фундаментальні знання допомагають дізнатися	KMP	O(n + m)	0.004653	Ні
Фундаментальні знання допомагають дізнатися	Rabin-Karp	O(n + m) у середньому, O(nm) у гіршому випадку	0.003064	Ні
Вибір методу представлення даних	Boyer-Moore	O(n)	0.000068	Так
Вибір методу представлення даних	KMP	O(n + m)	0.000252	Так
Вибір методу представлення даних	Rabin-Karp	O(n + m) у середньому, O(nm) у гіршому випадку	0.000455	Так

Висновок

На основі отриманих даних можна зробити висновки про найшвидшість та ефективність кожного з алгоритмів пошуку для обох текстів. Як і очікувалось, враховуючи часову складніть, алгоритм пошуку Boyer-Moore є найбільш ефективним, так як його часова складність - O(n).