Pagini recente » Istoria paginii links/algoritmi | Diferente pentru blog/square-root-trick intre reviziile 42 si 41
Nu exista diferente intre titluri.
Diferente intre continut:
sum += a[lo]
==
The query takes less than $k + n/k + k = 2k + n/k$ time. $2k + n/k$ is minimized when $k$ is <tex>O(\sqrt{n})</tex>. For $k = \sqrt{n}$ the query takes $O(\sqrt{n})$ time.
The query takes less than $k + n/k + k = 2k + n/k$ time. $2k + n/k$ is minimized when $k$ is $O(\sqrt{n})$. For $k = \sqrt{n}$ the query takes $O(\sqrt{n})$ time.
This trick also works for other associative operations, like: min, gcd, product etc.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
