1

考虑这样的一段代码：

for(i = 1, j ; i <= n ; i = j + 1) {
    j = n / (n / i);
    T = T + sqrt(n / i)
}

$$
T(n)=\sum_{i=1}^{n} \sqrt{\lfloor\frac{n}{i} \rfloor} [\lfloor\frac{n}{i}\rfloor 是第一次出现]=T_{i \le \sqrt{n}}(n)+T_{i> \sqrt{n}}(n)
$$

若 $1 \le i \le \sqrt{n}$，则：

$$
T_{i \le \sqrt{n}}(n) \le \sum_{i=1}^{\sqrt{n}} \sqrt{\lfloor \frac{n}{i} \rfloor} \le \sqrt{n}\int_{1}^{\sqrt n} \sqrt{\frac{1}{i}} di = 2\sqrt n (\sqrt{\sqrt n}-\sqrt{1}) \sim n^{\frac{3}{4}}
$$

若 $\sqrt{n} < i \le n$，则 $\lfloor \frac{n}{i} \rfloor \le \sqrt n$，也就是使得 $\lfloor \frac{n}{i} \rfloor$ 本质不同的 $i$ 有 $\sqrt{n}$ 种，则：

$$
T_{i > \sqrt{n}}(n) \sim \sqrt n \sqrt{\sqrt{n}}=n^{\frac{3}{4}}
$$
综上可得：
$$
T(n) \sim n^{\frac{3}{4}}
$$

2

$$
\sum_{i=\sqrt{n}}^{n}\left( \left \lfloor \frac{n}{i} \right \rfloor \right)^2 \le n^2\sum_{i=\sqrt{n}}^{n}\frac{1}{i^2} \le n^2 \int_{\sqrt{n}}^{n} \frac{1}{x^2} dx = n^2 \left(-\frac{1}{n}+\frac{1}{\sqrt{n}}\right) \sim n \sqrt n
$$