•Cosmin
|
|
« : August 11, 2011, 10:27:55 » |
|
|
|
|
Memorat
|
|
|
|
•mpatrascu
Strain
Karma: 85
Deconectat
Mesaje: 18
|
|
« Răspunde #1 : August 11, 2011, 16:27:47 » |
|
Pe toate 5 Să știi că 3-ul din lista ta nu prea seamănă cu cea de la IOI, deși pare. Multă lume a luat-o în direcții foarte greșite la IOI.
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #2 : August 11, 2011, 17:19:26 » |
|
La primele 3 se cere O(N) "pur"? Pentru ca imi vin in minte niste solutii cu hashuri.
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #3 : August 11, 2011, 20:35:16 » |
|
La prima, nu trebuie cumva sirul sa fie sortat ca sa iasa O (n) ? L.E.: De fapt la primele 2?
|
|
|
Memorat
|
|
|
|
•Magnus
Client obisnuit
Karma: 0
Deconectat
Mesaje: 57
|
|
« Răspunde #4 : August 11, 2011, 20:47:56 » |
|
merg cu hashuri in O(n) fara sortare
|
|
|
Memorat
|
|
|
|
•MciprianM
|
|
« Răspunde #5 : August 11, 2011, 20:54:08 » |
|
Eu ma gandeam la O(n) worst-case, si nu expected !
|
|
|
Memorat
|
|
|
|
•cr1st18
Strain
Karma: 1
Deconectat
Mesaje: 39
|
|
« Răspunde #6 : August 11, 2011, 21:21:59 » |
|
Sunt de acord cu Daniel, la primele doua probleme merge o rezolvare in O(n) cu hash-uri ...
|
|
|
Memorat
|
|
|
|
•crushack
|
|
« Răspunde #7 : August 11, 2011, 21:46:51 » |
|
Da, se pot face cu hash-uri, dar nu numai, daca nu vrei sa ai expected O(n) atunci poti sa faci cu radix-sort si cu o constanta frumusica (+ O(N) memorie ), la 3 n-am gasit solutie decat cu hashing , la 4 e dinamica si 5... ma gandesc
|
|
|
Memorat
|
|
|
|
•Cosmin
|
|
« Răspunde #8 : August 12, 2011, 00:47:39 » |
|
@mpatrascu, da, ai nevoie doar de 1 si 4 ca sa rezolvi 5, dar 2 si 3 sunt dragute ca tema de gandire
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #9 : August 13, 2011, 18:21:17 » |
|
Da, se pot face cu hash-uri, dar nu numai, daca nu vrei sa ai expected O(n) atunci poti sa faci cu radix-sort si cu o constanta frumusica (+ O(N) memorie ), la 3 n-am gasit solutie decat cu hashing , la 4 e dinamica si 5... ma gandesc Ma cam indoiesc ca poti caracteriza radix sort-ul ca fiind O(n) cu o constanta frumusica. Radix sort-ul e O(n * r) unde r e numarul de radix-uri.. care nu prea stiu cum sa-l iei astfel incat sa fie constant relativ la n si la magnitudinea numerelor. Daca iei dupa cifre de exemplu e O( N lg MAX ). In schimb, cand vine vorba de suffix arrays zice lumea ca e O(n) radix-ul. Nu stiu cum se accepta in general. Poate ne lumineaza cineva cu ocazia asta .
|
|
|
Memorat
|
|
|
|
•crushack
|
|
« Răspunde #10 : August 14, 2011, 15:10:49 » |
|
La radix complexitatea e O(N*Lmax), dar in cazul numerelor <=2 31 Lmax=31, deci complexitatea e O(N*31) => O(N)
|
|
|
Memorat
|
|
|
|
•Mishu91
|
|
« Răspunde #11 : August 14, 2011, 16:21:13 » |
|
La radix complexitatea e O(N*Lmax), dar in cazul numerelor <=2 31 Lmax=31, deci complexitatea e O(N*31) => O(N) Dupa rationamentul de mai sus, complexitatea O(NlogN) este acelasi lucru cu O(N), pentru orice N <= 2 31
|
|
|
Memorat
|
|
|
|
•klamathix
|
|
« Răspunde #12 : August 14, 2011, 17:04:08 » |
|
La radix complexitatea e O(N*Lmax), dar in cazul numerelor <=2 31 Lmax=31, deci complexitatea e O(N*31) => O(N) Din cate stiu eu, cand descrii un algoritm nu prea ai voie sa faci aproximari de genul. Complexitatea trebuie sa fie valabila pentru orice input, orice restrictii, orice instanta a problemei. Aici nici nu iti garanteaza nimeni ca numerele sunt pe 32 de biti. Despre complexitatea padurilor de multimi disjuncte, de exemplu, poti spune ca 'pentru orice valori fezabile din punct de vedere tehnic se poate aproxima cu O(1)' , dar nu ca este O(1). E O(log*) toata ziua. Asa stiam eu cel putin.
|
|
|
Memorat
|
|
|
|
•devilkind
|
|
« Răspunde #13 : August 14, 2011, 23:59:15 » |
|
In cazul radixsortului poti sa zici ca e O(N) deoarece numarul de operatii e "egal" cu volumul inputului. Mai exact, daca tu ai urmatoarea problema: Se citesc N caractere de la tastatura. Fiecare caracter este ori un numar de la 0-9 sau spatiu. Se cere sa sa spargi sirul de caractere dupa spatiu, sa iei numerele rezultate si sa le sortezi. Care e complexitatea daca folosesti radixsort?
E o confuzie care se face destul de mult in practica, si anume sa adaugi in complexitate valori date in enuntul problemei, pentru ca ai anumite constrangerii care iti spun ca valorea respectiva nu va depasi o constanta. Totusi in teorie astfel de constrangerii nu exista si de aceea cand se spune O(N), N este considerat ca fiind volumul datelor de intrare. Exemplu: Daca o sa luati cormenul la mana o sa observati ca problema rucsacului e clasificata ca fiind NP. De ce? Deoarece in analiza complexitatii intra in calcul valoarea maxima a numerelor, care creste exponential in raport cu numarul de caractere al datelor de intrare.
|
|
|
Memorat
|
|
|
|
•Vman
|
|
« Răspunde #14 : August 16, 2011, 11:59:49 » |
|
e O(N) pt ca numarul de bucketuri e constant si atunci cand calculezi complexitatea nu iei in calcul constantele, dat fiind ca daca N tinde la infinit constantele astea devin mult prea mici sa mai conteze. In practica in schimb daca ai o constanta maricica ar cam trebui sa incerci sa o reduci, un O(N^2) cu constanta 1/2 poate fi o solutie mai buna decat un O(NlogN) cu constanta mare atunci cand introduci constrangeri pt N
|
|
|
Memorat
|
|
|
|
|