|
Titlul: Solutii Scris de: Cosmin Negruseri din August 13, 2011, 06:29:35 Comentarii la http://infoarena.ro/blog/solutii
Titlul: Răspuns: Solutii Scris de: Parfene Narcis din August 23, 2011, 12:48:20 Presupunem ca in hash-table HT pastrez lista cu numerele din sir modulo p (p numar prim).
Deci HT[0] va pastra multiplii lui p. Si atunci la problema 1 nu va da complexitate O(n*n) daca sirul de numere dat are numai multipli de p? Titlul: Răspuns: Solutii Scris de: Duta Vlad din August 23, 2011, 15:39:00 Complexitatea medie este O(N), ce spui tu este complexitatea worst-case.
Si exista variante de hashing care garanteaza O(N) pe worst-case (perfect hashing, linear hashing, etc) |