|
Titlul: sortare stringuri Scris de: Mihai Alex Ionescu din Iulie 07, 2009, 11:28:30 Ok problema ar suna cam asa
Se dau N siruri de caractere Unicode de lungime maxim M , N si M <= 1000000. Sa se sorteze crescator in functie de indicele caracterului Mie imi vine in cap quicksort in O (N * M * logN), sau eventual un trie , in O(N*M) Exista ceva mai rapid ? Titlul: Răspuns: sortare stringuri Scris de: Emanuel Cinca din Iulie 07, 2009, 12:24:23 Sa se sorteze fiecare sir sau toate sirurile?
Daca ti se dau N stringuri de lungime maxim M atunci poti sorta cu quicksort si mai rapid cu sort() din STL. Daca trebuie sa sortezi fiecare 1....N string de lungime M, nu am idee mai rapida decat ai spus tu. Titlul: Răspuns: sortare stringuri Scris de: Andrei Grigorean din Iulie 07, 2009, 12:45:27 Pai oricum nu poti mai bine de O(N*M) pentru ca atat iti ia citirea datelor.
Titlul: Răspuns: sortare stringuri Scris de: Mihai Alex Ionescu din Iulie 07, 2009, 16:27:18 Sa se sorteze fiecare sir sau toate sirurile? Daca ti se dau N stringuri de lungime maxim M atunci poti sorta cu quicksort si mai rapid cu sort() din STL. Daca trebuie sa sortezi fiecare 1....N string de lungime M, nu am idee mai rapida decat ai spus tu. Da, toate sirurile. Pai se poate sorta mai repede decat N*M*logN? sort'u din STL scoate mai putin pt stringuri? Adica .. nu face tot NlogN comparatii ? Si ca sa compari 2 siruri ar lua O(M). Si m-ar interesa si ceva materiale utile si succinte despre arbori de sufixe, am gasit si eu articole (art lui Ukkonen) dar sunt mult prea mari si greoaie. Titlul: Răspuns: sortare stringuri Scris de: Sima Cotizo din Iulie 08, 2009, 11:51:04 Pai tu cu un trie ai zis ca scoti O(N*M). Cum si citirea tot O(N*M) este, asta e complexitatea cea mai buna :) (asta voia Wef sa-ti zica)
|