Yet Another Programmer

主要是因为看了这篇blog突然想到的。这个筛法求素数的程序想必每个学编程的人都写过，几乎是最经典的算法之一了，虽然似乎没什么用。但好像的确没见过对这个古老算法的严格分析。一时好奇，就想把这个算法纳入大O的框架之中……不管怎么样，先拿出代码再说

require'benchmark'
 
def sievePerformance(n)
    r = Benchmark.realtime() do
        sieve = Array.new(n,true)
        sieve[0..1] = [false,false]
        2.upto(n) do |i|
            if sieve[i]
                (2*i).step(n,i) do |j|
                    sieve[j] = false
                end
            end
        end
    end
    r
end

这段代码抄自前面Robert C.Martin先生的blog，对筛法作性能测试。初看起来，程序的主体是二重循环，因此算法的复杂性好像是O(N²)之类的玩意？要么是O(NlnN)？
 
下图是Ruby自带的benchmark模块测量的结果，上限N从10000到500000，步长20000。Rober C.Martin的文章里也有一张图，是从1000000到5000000，从图中可以看到，他电脑的性能远胜于我，我要是从1000000到5000000这么跑一遍，花儿都谢了……总之，实测的结果是：这个算法的性能基本上是线性的。出于对ruby这样的解释型语言的某种不信任，我又把这段程序用C++重写了一遍，拿C标准库提供的clock函数测量时间，结果在N小于10000000的时候，基本上呈线性，但再往后花费的时间就开始超过线性增长了。

下面我给一个比较粗略的分析，解释为什么这个算法的复杂度表现为线性。首先，我认为主要花费时间的是对sieve数组的读写，循环变量的增加应该可以忽略。如果p<N是素数，那么就要进入内循环将i的倍数“挖掉”，也就是对sieve的相应元素赋值，要进行[N/p]-1次。这样就得到总共的赋值次数S为：



其中p为素数。显然



数论中有个Mertens定理可以估计上面括号中的和式，结果为



其中c是一个常数。可以看到，在N很大时和式的主要部分为NlnlnN。而lnlnN是一个增长极慢的函数，lnln10⁵=2.44，lnln10⁹=2.91，几乎就可以当常数处理（至少在32位无符号整数范围内）。其他的一些项，比如循环变量的步进，都是O(N)，这也就不难理解整个程序的性能是几乎是O(N)了。




Update：上面的代码有个很明显的问题，就是内循环应该从i*i开始，而不是2*i，这样对于比较大的N，性能提高很明显（接近一半）。另外一个可改进的地方是外层循环的upto(n)，可以改为upto(Integer(Math.sqrt(n))，其实这两个改动效果是重叠的，任意改一个就差不多了。赋值次数S应为：



结果为：



可以看到效率的提升是很明显的，毕竟lnln2³²也才不到3.1，ln2约为0.7。