Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Cautari ortogonale: structuri de date si aplicatii  (Citit de 10494 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Februarie 20, 2009, 02:43:23 »

Comentarii la articolul Cautari ortogonale: structuri de date si aplicatii
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
ads13
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #1 : 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?
Memorat
batista
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 7



Vezi Profilul
« Răspunde #2 : 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
Memorat
fluture.godlike
Strain
*

Karma: -6
Deconectat Deconectat

Mesaje: 30



Vezi Profilul
« Răspunde #3 : 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? Smile
Multumesc!

L.E. Am aflat, multumesc!
« Ultima modificare: Ianuarie 24, 2016, 10:03:46 de către Gafton Mihnea Alexandru » Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines