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?
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena
Afişează mesaje