Logowanie

Który algorytm szybszy?

pytanie zadane 18 maja 2017 w C i C++ przez Ala123456 Użytkownik (760 p.)

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

komentarz 18 maja 2017 przez adrian17 Ekspert (349,240 p.)

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

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

2 odpowiedzi

odpowiedź 18 maja 2017 przez WilmaOlcho Obywatel (1,740 p.)

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ść.

komentarz 18 maja 2017 przez niezalogowany

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

komentarz 18 maja 2017 przez WilmaOlcho Obywatel (1,740 p.)

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?

komentarz 18 maja 2017 przez niezalogowany

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

komentarz 18 maja 2017 przez WilmaOlcho Obywatel (1,740 p.)

W takim razie :) Lecę do lektury!

odpowiedź 18 maja 2017 przez niezalogowany

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

komentarz 18 maja 2017 przez Ala123456 Użytkownik (760 p.)

Wyszykiwać najkrótsza sciezke

komentarz 18 maja 2017 przez niezalogowany

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

komentarz 18 maja 2017 przez Ala123456 Użytkownik (760 p.)

algorytm Dijkstry. graf macierz 6 na 6

komentarz 18 maja 2017 przez niezalogowany

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

komentarz 18 maja 2017 przez Ala123456 Użytkownik (760 p.)

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

Podobne pytania

0 głosów

1 odpowiedź 323 wizyt

Szybszy i wydajniejszy sposób

pytanie zadane 23 kwietnia 2017 w Inne języki przez Mar-Ch Nowicjusz (150 p.)

0 głosów

1 odpowiedź 163 wizyt

Który program szybszy

pytanie zadane 5 stycznia 2016 w C i C++ przez sebi10 Użytkownik (590 p.)

0 głosów

1 odpowiedź 1,372 wizyt

Skrypt i Algorytm

pytanie zadane 17 października 2017 w Matematyka, fizyka, logika przez TakiT4mN1ck Nowicjusz (120 p.)

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...