Witam. Który algorytm wyszukiwania wzorca jest szybszy Karpa-Rabina czy Dijskstry?
0
1
Na Wikipedii masz napisaną złożoność:
1:Algorytm Karpa-Rabina
2.Algorytm Dijkstry
Gdybys nie wiedzial co to zlozonosc to mozesz tutaj przeczytac:
Zlozonsc obliczeniowa
4
A ja powiem przekornie że nie da się odpowiedzieć na takie pytanie. Można stwierdzić na przykład który ma wyższy/niższy rząd złożoności obliczeniowej. Ale "szybkość" to można ocenić tylko empirycznie dla konkretnych danych i konkretnego sprzętu i konkretnego wykonania. Dla odpowiedniej architektury algorytm asymptotycznie "gorszy" może być szybszy i vice versa. Podobnie dla odpowiednich rozmiarów danych.
0
algorytm Dijkstry nie służy do znajdowania wzorca, a obliczania najkrótszej ścieżki ze źródła do pozostałych wierzchołków w grafie