编程珠玑(续) 8.2分
读书笔记 第12页
邻家の低端码农

第二题的C问中,O(nloglogn)的复杂度可以这么推出:

p = 2;
while (p <= n)
{
	for (i = 2 * p; i <= n; i += p)
	 x[i] = 0;

	do
		p++;
	while (!x[p]);
}

这是经过处理后的代码,主要是便于分析。容易知道,只需要分析x[i] = 0;的运行次数即可。 T(n) = n/2 + n/3 + ... + n/p, 其中p为不大于n最大的素数。然后我们有 T(n) = n(1/2 + 1/3 +..+ 1/p) *fix:吃饭时突然想到刚才右半部分的证明是不对的,特此更正下。 右边的其实是有专业术语的,称之为:素数调和级数,渐进于O(loglogn).欧拉给出了一个下界(非函数增长上的渐进下界,不过可以由此得到Omega)。 http://en.wikipedia.org/wiki/Prime_harmonic_series 如果 log_{a}n = O(logn) => log_{b}n = O(logn),其中a,b均>1 对于d,目前已知最好的方法是进行素性测试。该测试基于费马小定理,并且可以在现行时间内完成测试,不过没有100%正确的概率。然后可以进行大量独立重复测试,将概率控制在接受范围之内。

0
《编程珠玑(续)》的全部笔记 13篇
豆瓣
免费下载 iOS / Android 版客户端