Pagini recente » Diferente pentru blog/dexonline intre reviziile 6 si 3 | Istoria paginii blog/square-root-trick | Diferente pentru problema/bunicu intre reviziile 5 si 9 | Diferente pentru problema/cuburi4 intre reviziile 6 si 5 | Diferente pentru blog/square-root-trick intre reviziile 101 si 102
Nu exista diferente intre titluri.
Diferente intre continut:
return s
==
Each query takes less than $k + n/k + k = 2k + n/k$ time. For $k = sqrt(n)$ we get a $O(sqrt(n))$ time complexity query.
Each query takes on average $k/2 + n/k + k/2 = k + n/k$ time. This is minimized for $k = sqrt(n)$. So we get a $O(sqrt(n))$ time complexity query.
This trick also works for other associative operations, like: min, gcd, product etc.
Diferente intre securitate:
Topicul de forum nu a fost schimbat.
