Sorry if this has already been answered before, I just couldn't find the answer anywhere.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3904 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3494 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | maroonrk | 3350 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 159 |
5 | awoo | 157 |
5 | adamant | 157 |
7 | -is-this-fft- | 156 |
8 | nor | 154 |
9 | TheScrasse | 153 |
10 | Dominater069 | 152 |
Sorry if this has already been answered before, I just couldn't find the answer anywhere.
Название |
---|
It's n times a partial sum of [harmonic series](https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)#Partial_sums), so it's nlogn.
Oh, I didn't notice that. Thanks for the answer!
There is also proofs for why partial sum of harmonic series is like that.
If you meant that you want to get the complexity of computing this (with floor division), you can do so in $$$O(\sqrt n)$$$ by noting that there can be at most $$$2 \sqrt n$$$ distinct terms in the sum.
No, I was specifically looking at this problem — https://codeforces.net/contest/1558/problem/B. I solved it with that complexity with a seemingly simpler solution than what the editorial offered. At least I think it was that complexity.
Also you can also calculate the floor sum function in $$$O(\sqrt[3]{n})$$$
One of the way is to approximate $$$O(\sqrt[3]{n})$$$ slopes in the function $$$y = f(x) = \left \lfloor \frac{n}{x} \right \rfloor$$$
The other way is to split into $$$O(\sqrt[3]{n})$$$ parts of $$$[A, 2A)$$$
yes, my favorite Dirichlet hyperbola method
That's n(1/2 + 1/3 + ...) 1/2 + 1/3 + ... + 1/n is the harmonic series and equals with aproximative log(n). So the complexitate will be O(nlog(n))
Here's how you can approximate that it is $$$nlogn$$$:
$$$\frac{n}{1} + \frac{n}{2} + ... + \frac{n}{n} = $$$
$$$n(\frac{1}{1} + \frac{1}{2} +\frac{1}{3}+ \frac{1}{4} + \frac{1}{5} + \frac{1}{6}+... +\frac{1}{n} \leq $$$
$$$ \leq n(\frac{1}{1} + \frac{1}{2} + \frac{1}{2} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{4} + \frac{1}{8} + \frac{1}{8} ... + \frac{1}{2^k} = $$$
$$$ = n(\frac{1}{1} + \frac{1}{2^1} + \frac{1}{2^1} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^2} + \frac{1}{2^3} + \frac{1}{2^3} ... + \frac{1}{2^k} $$$
$$$2^k \approx n \Rightarrow k \approx log_2n$$$
If we add all the components with the same power of 2, we get $$$1$$$. Because there are $$$\approx log_2n$$$ powers, we get that the sum is $$$\approx nlog_2n$$$
I didn't actually do this myself, but there's an interesting comment about bounding the harmonic numbers here. Jensen's inequality + some elementary calculus should do the trick (it's quite nice)
You can always bound with trapezoidal rule and some calc too, if you prefer
galen_colin explained it here here