Pagini recente » Diferente pentru problema/teste intre reviziile 20 si 19 | Diferente pentru problema/matrita intre reviziile 42 si 6 | Diferente pentru utilizator/alex_bucevschi intre reviziile 53 si 18 | Monitorul de evaluare | Diferente pentru tree-decompositions intre reviziile 31 si 32
Nu exista diferente intre titluri.
Diferente intre continut:
Complexitatea finala: $O(M*sqrt(N)*log(N))$.
O imbunatatire pentru aceasta metoda o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau si nu cel cu inaltimea maxima. Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si in figura urmatoare :
O imbunatatire pentru aceasta metoda o reprezinta $heavy path decomposition$, care se foloseste de acelasi algoritm, cu exceptia faptului ca fiul ales pentru determinarea unui lant este cel cu numar maxim de noduri in subarborele sau (heavy) si nu cel cu inaltimea maxima (longest). Prin urmare, numarul maxim de lanturi prin care se trece pentru a ajunge de la un nod la radacina este cel mult $O(log(N))$ dupa cum se poate vedea si in figura urmatoare :
_Fig. 3 : Fiecare nod apartine unui singur lant. Lanturile sunt reprezentate de muchii solide._
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
