algorytm.org

Zliczanie różnic między ciągami

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Forum www.algorytm.org :: Pozostałe
Witaj Gość   
[Zarejestruj się]  
[Zaloguj się]
Zamieść odpowiedź
 Zliczanie różnic między ciągami

photo
Witam,

Natknąłem się na pewien problem przy wymyślaniu jednego algorytmu.
Męczę się już z tydzień i nie przychodzi mi do głowy żadne efektywne rozwiązanie mojego problemu.

Danych jest n ciągów liczbowych a. Problem polega na znalezieniu dla każdego ciągu a(i) ciągu a(j) gdzie i != j. i j Ciągi a(i) i a(j) muszą mieć możliwie najwięcej wspólnych elementów.
Np.:
a : 1, 2, 3, 2, 5, 8
b : 2, 3, 3, 5, 11
Dla tych dwóch ciągów wspólnych elementów jest 3 : 2, 3, 5.
Być może w jakiś sposób pomocna jest informacja, że ciągi wejściowe
są posortowane niemalejąco.

Zliczanie naiwne zajmuje złożoność O(n^2), ale być może istnieje jakiś szybszy sposób ? Może ktoś pomóc ?

Pozdrawiam.
Cytuj
Zamieść odpowiedź Strona # 
Szybka odpowiedź

Kod:    


Powered by ccBoard