|
Titlul: Ajutor algoritm Scris de: Radu Chichi din Aprilie 18, 2011, 16:16:17 Puteti va rog sa-mi descrieti solutia de complexitate O(n*Logn) la aceasta problema ? Multumesc !
Citat din mesajul lui: Admitere unibuc Un cuvânt este anagramã a altui cuvânt dacã este format din exact aceleaºi litere, aranjate într-o altã ordine. Exemplu: caras si scara. b) Dându-se o mulþime de n cuvinte peste alfabetul {a ,........, z} sã se verifice dacã printre elementele mulþimii date existã anagrame. Titlul: Răspuns: Ajutor algoritm Scris de: George Marcus din Aprilie 18, 2011, 16:41:40 Ma gandesc ca e ceva de genul:
Pentru fiecare cuvant, ii sortezi literele componente alfabetic. Apoi, sortezi alfabetic toate cuvintele intre ele. In final, verifici daca exista cuvinte egale pe pozitii consecutive. Complexitatea O(N*logN) vine de la sortare. Titlul: Răspuns: Ajutor algoritm Scris de: truenight din Aprilie 18, 2011, 16:47:44 Daca am folosi un array 2D in care, pentru fiecare cuvant, retinem de cate ori se repeta fiecare litera din cuvant si dupa aia comparam, s-ar incadra in O(N*logN)?
Titlul: Răspuns: Ajutor algoritm Scris de: George Marcus din Aprilie 18, 2011, 17:03:59 A ta e O(N*nr de litere din alfabet * log (nr de litere)) . Daca cuvintele sunt mai lungi decat numarul de litere din alfabet, atunci e mai eficienta decat solutia mea pentru ca ai de facut mai putine comparatii la sortare. Insa, pentru stringuri exista functii predefinite, deci e mai comod.
Titlul: Răspuns: Ajutor algoritm Scris de: Cosmin-Mihai Tutunaru din Mai 05, 2011, 00:25:54 Ma gandesc ca e ceva de genul: Pentru fiecare cuvant, ii sortezi literele componente alfabetic. Apoi, sortezi alfabetic toate cuvintele intre ele. In final, verifici daca exista cuvinte egale pe pozitii consecutive. Complexitatea O(N*logN) vine de la sortare. Vezi că soluţia ta are o complexitate O(N * lngCuvânt * (log(N) + log(lngCuvânt)) Compararea a două cuvinte nu se face în timp constant. Se face în O(lungimeCuvânt) Titlul: Răspuns: Ajutor algoritm Scris de: George Marcus din Mai 05, 2011, 14:42:38 Da, ai dreptate. Eu am considerat ca se poate neglija lungimea cuvantului, iar daca e prea mare atunci se trece la cealalta varianta.
Titlul: Răspuns: Ajutor algoritm Scris de: Petru Trimbitas din Mai 05, 2011, 14:47:26 Puteti va rog sa-mi descrieti solutia de complexitate O(n*Logn) la aceasta problema ? Multumesc ! Citat din mesajul lui: Admitere unibuc Un cuvânt este anagramã a altui cuvânt dacã este format din exact aceleaºi litere, aranjate într-o altã ordine. Exemplu: caras si scara. b) Dându-se o mulþime de n cuvinte peste alfabetul {a ,........, z} sã se verifice dacã printre elementele mulþimii date existã anagrame. Pentru fiecare cuvant il sortezi si il bagi intr-un hash. Daca il mai gasesti in hash inseamna ca ai anagrama. |