Wątek przeniesiony 2017-05-18 19:32 z C/C++ przez kq.

Który algorytm jest szybszy?

0

Witam. Który algorytm wyszukiwania wzorca jest szybszy Karpa-Rabina czy Dijskstry?

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1