考虑这样的一段代码：

1
2
3
4

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{lfloorfrac{n}{i} rfloor} [lfloorfrac{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 = 2sqrt 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