Który algorytm szybszy?

Question

Witam. Ktory algorytm jest szybszy(czas operacji) Karpa-Rabina czy naiwny?

Comments

Może źle zrozumiałem, ale...

Co ma algorytm wyszukiwania podciągów do szukania ścieżki na grafie?

Answer 1

Nie znam tych algorytmów, ale znam łatwy sposób by sprawdzić.
Stwórz funkcję testującą zwracającą czas który upłynął korzystając z <chrono>
Porównaj oba algorytmy dla takich samych wartości, i powtarzaj ten test wielokrotnie (inną funkcją) aż uzyskasz satysfakcjonujący Cię wynik + kilkaset więcej by mieć pewność.

Comments

A nie sądzisz, że lepiej i łatwiej jest porównać złożoności obliczeniowe danych algorytmów?

---

W zasadzie, tak też powinno być, ale czy złożoność obliczeniowa da rzeczywiście miarodajne wyniki, kiedy mimo wszystko algorytm może zachowywać się całkowicie różnie w zależności od danych jakie są do niego wprowadzane?

---

Ale złożoność obliczeniową wylicza się dla konkretnych zestawów danych (wors, average, best case)

---

W takim razie :) Lecę do lektury!

Answer 2

Zgaduję, że Rabina (bo "naiwny" jest naiwny), ale nie napisałeś co ma rozwiązywać algorytm...

Comments

Wyszykiwać najkrótsza sciezke

---

No dobrze, ale mówimy o jakiej sytuacji testowej (o jakich danych wejściowych) i co rozumiesz przez "algorytm naiwny"

---

algorytm Dijkstry. graf macierz 6 na 6

---

Nie nazwałbym dijkstry metodą nawiną, o jakim grafie mówimy? Skierowanym, z wagami (bez wag, dodatnie/ujemne)?

---

Przepraszam pomysliły mi się zadania w tym mam wszykac wzorzec w tekscie macierz 3X3 z literami ABC