Математика!
Вообще тут будет какое-то доказательство каких-то общеизвестных фактов, которые помогут вам. Можете просить доказать то, что вам надо.
\(\displaystyle{} \frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} \leq n log (n)\\ \)
Пусть \(k\) - минимальное такое целое число, что \(2^k \geq n\)
Тогда верно, что:
\(\displaystyle{} \frac{n}{1}+\frac{n}{2}+\cdots+\frac{n}{n} \leq \frac{2^k}{1} + \frac{2^k}{2} + \cdots + \frac{2^k}{n} \leq \frac{2^k}{1} + \frac{2^k}{2} + \cdots + \frac{2^k}{2^k}\)
Теперь двайте разобьем это на такие блоки:
\(\displaystyle{} \frac{2^k}{1} = 2^k\)
\(\displaystyle{} \frac{2^k}{2} + \frac{2^k}{3} \leq \frac{2^k}{2} + \frac{2^k}{2} \leq 2^k \)
\(\displaystyle{} \cdots\)
\(\displaystyle{} \frac{2^k}{2^x} + \frac{2^k}{2^x + 1} + \cdots + \frac{2^k}{2^{x+1}-1} \leq \frac{2^k}{2^x} + \frac{2^k}{2^x} + \cdots + \frac{2^k}{2^x} \leq 2^k\)
\(\displaystyle{} \cdots\)
Таким образом, мы получим \(k\) групп, сумма в каждой из которых не больше чем \(2^k\)
а значит вся сумма лежит в \(O(n \log(n)))\)
Факт 1:
\(\displaystyle{} \frac{n}{1} + \frac{n}{2} + \cdots + \frac{n}{n} \leq n log (n)\\ \)
Пусть \(k\) - минимальное такое целое число, что \(2^k \geq n\)
Тогда верно, что:
\(\displaystyle{} \frac{n}{1}+\frac{n}{2}+\cdots+\frac{n}{n} \leq \frac{2^k}{1} + \frac{2^k}{2} + \cdots + \frac{2^k}{n} \leq \frac{2^k}{1} + \frac{2^k}{2} + \cdots + \frac{2^k}{2^k}\)
Теперь двайте разобьем это на такие блоки:
\(\displaystyle{} \frac{2^k}{1} = 2^k\)
\(\displaystyle{} \frac{2^k}{2} + \frac{2^k}{3} \leq \frac{2^k}{2} + \frac{2^k}{2} \leq 2^k \)
\(\displaystyle{} \cdots\)
\(\displaystyle{} \frac{2^k}{2^x} + \frac{2^k}{2^x + 1} + \cdots + \frac{2^k}{2^{x+1}-1} \leq \frac{2^k}{2^x} + \frac{2^k}{2^x} + \cdots + \frac{2^k}{2^x} \leq 2^k\)
\(\displaystyle{} \cdots\)
Таким образом, мы получим \(k\) групп, сумма в каждой из которых не больше чем \(2^k\)
а значит вся сумма лежит в \(O(n \log(n)))\)