一道奇怪的数学题据说有人一眼就看
证明:先证Σ(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+。。。中,把1/3变成1/2,使得两个1/2加起来凑成一个1;再把1/5,1/6和1/7全部变成1/4,这样四个1/4加起来又是一个1。 把所有1/2^k的后面^k-1项全部扩大为1/2^k,使得这2^k个分式加起来是一个1。现在,1+1/2+。。。+1/n里面产生的1的个数我们决定于小于n的数有多少个2的幂即可。显然,经过数的扩大后原式各项总和为log n。 O(logn)是Σ(1/n)的复杂度上界。
再证,Σ(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+。。。中,我们把1/...全部
证明:先证Σ(1/n)=O(log n)。在式子1+1/2+1/3+1/4+1/5+。。。中,把1/3变成1/2,使得两个1/2加起来凑成一个1;再把1/5,1/6和1/7全部变成1/4,这样四个1/4加起来又是一个1。
把所有1/2^k的后面^k-1项全部扩大为1/2^k,使得这2^k个分式加起来是一个1。现在,1+1/2+。。。+1/n里面产生的1的个数我们决定于小于n的数有多少个2的幂即可。显然,经过数的扩大后原式各项总和为log n。
O(logn)是Σ(1/n)的复杂度上界。
再证,Σ(1/n)=Ω(log n)。在式子1+1/2+1/3+1/4+1/5+。。。中,我们把1/3变成1/4,使得两个1/4加起来凑成一个1/2;再把1/5,1/6和1/7全部变成1/8,这样四个1/8加起来又是一个1/2。
把所有/2^k的前面2^k-1项全部缩小为1/2^k,使得这2^k个分式加起来是一个1/2。现在,1+1/2+。。。+1/n里面产生的1/2的个数决定于小于n的数有多少个2的幂即可。显然,经过数的缩小后原式各项总和为1/2*logn。
Ω(logn)是Σ(1/n)的复杂度下界。
。收起