|
Titlul: Cautari ortogonale: structuri de date si aplicatii Scris de: Stefan Istrate din Februarie 20, 2009, 02:43:23 Comentarii la articolul Cautari ortogonale: structuri de date si aplicatii (http://infoarena.ro/cautari-ortogonale)
Titlul: Răspuns: Cautari ortogonale: structuri de date si aplicatii Scris de: Adriana Pitea din Decembrie 01, 2010, 17:51:17 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?
Titlul: Răspuns: Cautari ortogonale: structuri de date si aplicatii Scris de: UPB-Oprea-Cosmin-Dumitru din Decembrie 29, 2014, 17:18:28 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 (http://www.csd.uwo.ca/~moreno/CS433-CS9624/Resources/master.pdf) Titlul: Răspuns: Cautari ortogonale: structuri de date si aplicatii Scris de: Gafton Mihnea Alexandru din Ianuarie 13, 2016, 10:36:51 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! |