当前位置 博文首页 > ApocalypseTq的博客:P1035 [NOIP2002 普及组] 级数求和 题解
在算模拟做法(做法1)的时间复杂度时,我想到了一种新的数论做法(做法2),检查了一遍题解发现没有这种做法,于是我写了这篇题解。
1.模拟
这种做法的思路是枚举nn从1开始,直到Sn>kSn>k结束,只需要一个循环即可实现。
代码:
#include<cstdio>
int main() {
int k,n=0;
scanf("%d",&k);
for(double Sn=0;Sn<=k;++n,Sn+=1.0/n);
printf("%d",n);
return 0;
}
空间复杂度O(1)O(1)
时间复杂度O(e^{k-\gamma})O(ek?γ)(求法见做法2)
(如果那个\gammaγ可以约去的话,应该是O(e^k)O(ek),但并不知道可不可以约去)
2.数论(调和级数)
关于调和级数的姿势,点这里。
已知Sn=1+1/2+1/3+...+1/n=\sum_{k=1}^{n}\frac{1}{k}Sn=1+1/2+1/3+...+1/n=∑k=1n?k1?。
明显地,SnSn为第nn个调和数。
欧拉推导过求调和级数有限多项和的表达式为\sum_{k=1}^{n}\frac{1}{k}=\ln(n+1)+\gamma∑k=1n?k1?=ln(n+1)+γ,我们拿过来用即可。(\gammaγ约等于0.5772156649)
我们需要满足Sn>kSn>k,即满足\ln(n+1)+\gamma>kln(n+1)+γ>k,化简得n>e^{k-\gamma}-1n>ek?γ?1。
我们只需求满足上式的最小的nn,所以n=e^{k-\gamma}+0.5n=ek?γ+0.5(四舍五入),即模拟做法的时间复杂度为O(e^{k-\gamma})O(ek?γ)。
关于\gammaγ(欧拉-马歇罗尼常数)的姿势,点这里。
代码:
在算模拟做法(做法1)的时间复杂度时,我想到了一种新的数论做法(做法2),检查了一遍题解发现没有这种做法,于是我写了这篇题解。
1.模拟
这种做法的思路是枚举nn从1开始,直到Sn>kSn>k结束,只需要一个循环即可实现。
代码:
#include<cstdio>
int main() {
int k,n=0;
scanf("%d",&k);
for(double Sn=0;Sn<=k;++n,Sn+=1.0/n);
printf("%d",n);
return 0;
}
空间复杂度O(1)O(1)
时间复杂度O(e^{k-\gamma})O(ek?γ)(求法见做法2)
(如果那个\gammaγ可以约去的话,应该是O(e^k)O(ek),但并不知道可不可以约去)
2.数论(调和级数)
关于调和级数的姿势,点这里。
已知Sn=1+1/2+1/3+...+1/n=\sum_{k=1}^{n}\frac{1}{k}Sn=1+1/2+1/3+...+1/n=∑k=1n?k1?。
明显地,SnSn为第nn个调和数。
欧拉推导过求调和级数有限多项和的表达式为\sum_{k=1}^{n}\frac{1}{k}=\ln(n+1)+\gamma∑k=1n?k1?=ln(n+1)+γ,我们拿过来用即可。(\gammaγ约等于0.5772156649)
我们需要满足Sn>kSn>k,即满足\ln(n+1)+\gamma>kln(n+1)+γ>k,化简得n>e^{k-\gamma}-1n>ek?γ?1。
我们只需求满足上式的最小的nn,所以n=e^{k-\gamma}+0.5n=ek?γ+0.5(四舍五入),即模拟做法的时间复杂度为O(e^{k-\gamma})O(ek?γ)。
关于\gammaγ(欧拉-马歇罗尼常数)的姿势,点这里。
代码:
#include<cstdio>
#include<cmath>
const double gamma=0.5772156649;
int main() {
int k,n;
scanf("%d",&k);
n=exp(k-gamma)+0.5;
printf("%d",n);
return 0;
}
空间复杂度O(1)O(1)
时间复杂度O(???)O(???)
(因为不知道math.h头文件中的exp函数的时间复杂度,所以不知道时间复杂度)
未解决的问题
1.时间复杂度O(e^{k-\gamma})O(ek?γ)中的\gammaγ可不可以约去?
2.math.h头文件中的exp函数的时间复杂度为多少?
3.有dalao说\gammaγ是极限意义下的,不能直接k-\gammak?γ是什么意思?
最后,