如何求一个数列的上界

解：an=1/(3+1)+1/(3²+1)++1/(3^n+1)
<1/3+1/3²+1/3³++1/3^n
=(1-1/3^n)/2<1/2
又an=1/(3+1)+1/(3²+1)++1/(3^n+1)>1/(1+3)=1/4
于是1/4<an<1/2
所以an上界是1/2 ，下界是1/4

考虑外层循环循环了n次，第i次内层循环循环了⌊n/i⌋次，因此时间复杂度为
O(n+n/2+n/3+n/4++n/n)=O(n(1+1/2+1/3+1/4++1/n))
根据调和级数的知识，由欧拉得到的结论：1+1/2+1/3+1/4++1/n=ln(n)+γ，其中γ为欧拉常数，近似值为γ≈057721。
因此我们可以得出程序的时间复杂度为
O(n ln n+nγ)
考虑到γ十分小，ln n=log_e n，其中e≈27≈2，因而程序的渐进时间复杂度约为O(nlogn)。

---