Cautari ortogonale: structuri de date si aplicatii

[•stef2n]

Comentarii la articolul Cautari ortogonale: structuri de date si aplicatii

[•ads13]

Salut! am avut de rezolvat de curand o problema privind k-d trees; dupa ce am citit articolul, as avea o intrebare; cum demonstrezi ca relatia de recurenta rezolva Q(n)=O(sqrt(n))? Pentru n=1 e ok, dar apoi cum calculam Q(n)=2+2Q(n/4) daca avem n/4<1? Am incercat sa scriu recurenta si sa pun conditie de oprire in momentul in care fractia tinde la 1, dar am obtinut Q(log(sqrt(n))) in loc de O(sqrt(n)). idei?

[•batista]

Folosind Teorema Master complexitatea recurentei Q(n) = 2*Q(n/4) + 2 este O(sqrt(n)).
http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf

[•fluture.godlike]

Salut!
"insa acest neajuns il putem evita folosind impreuna cu arborele indexat binar si o tabela de dispersie. Facand aceasta folosim numai O(nr log2 N) spatiu pentru nr puncte in plan inserate in structura,"
Poate cineva sa detalieze asta va rog?
Multumesc!

L.E. Am aflat, multumesc!