Yet Another Programmer

主要是因?yàn)榭戳?a >這篇blog突然想到的。這個(gè)篩法求素?cái)?shù)的程序想必每個(gè)學(xué)編程的人都寫過(guò)，幾乎是最經(jīng)典的算法之一了，雖然似乎沒什么用。但好像的確沒見過(guò)對(duì)這個(gè)古老算法的嚴(yán)格分析。一時(shí)好奇，就想把這個(gè)算法納入大O的框架之中……不管怎么樣，先拿出代碼再說(shuō)

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，對(duì)篩法作性能測(cè)試。初看起來(lái)，程序的主體是二重循環(huán)，因此算法的復(fù)雜性好像是O(N²)之類的玩意？要么是O(NlnN)？
?
下圖是Ruby自帶的benchmark模塊測(cè)量的結(jié)果，上限N從10000到500000，步長(zhǎng)20000。Rober C.Martin的文章里也有一張圖，是從1000000到5000000，從圖中可以看到，他電腦的性能遠(yuǎn)勝于我，我要是從1000000到5000000這么跑一遍，花兒都謝了……總之，實(shí)測(cè)的結(jié)果是：這個(gè)算法的性能基本上是線性的。出于對(duì)ruby這樣的解釋型語(yǔ)言的某種不信任，我又把這段程序用C++重寫了一遍，拿C標(biāo)準(zhǔn)庫(kù)提供的clock函數(shù)測(cè)量時(shí)間，結(jié)果在N小于10000000的時(shí)候，基本上呈線性，但再往后花費(fèi)的時(shí)間就開始超過(guò)線性增長(zhǎng)了。

下面我給一個(gè)比較粗略的分析，解釋為什么這個(gè)算法的復(fù)雜度表現(xiàn)為線性。首先，我認(rèn)為主要花費(fèi)時(shí)間的是對(duì)sieve數(shù)組的讀寫，循環(huán)變量的增加應(yīng)該可以忽略。如果p<N是素?cái)?shù)，那么就要進(jìn)入內(nèi)循環(huán)將i的倍數(shù)“挖掉”，也就是對(duì)sieve的相應(yīng)元素賦值，要進(jìn)行[N/p]-1次。這樣就得到總共的賦值次數(shù)S為：



其中p為素?cái)?shù)。顯然



數(shù)論中有個(gè)Mertens定理可以估計(jì)上面括號(hào)中的和式，結(jié)果為



其中c是一個(gè)常數(shù)?？梢钥吹?，在N很大時(shí)和式的主要部分為NlnlnN。而lnlnN是一個(gè)增長(zhǎng)極慢的函數(shù)，lnln10⁵=2.44，lnln10⁹=2.91，幾乎就可以當(dāng)常數(shù)處理（至少在32位無(wú)符號(hào)整數(shù)范圍內(nèi)）。其他的一些項(xiàng)，比如循環(huán)變量的步進(jìn)，都是O(N)，這也就不難理解整個(gè)程序的性能是幾乎是O(N)了。




Update：上面的代碼有個(gè)很明顯的問(wèn)題，就是內(nèi)循環(huán)應(yīng)該從i*i開始，而不是2*i，這樣對(duì)于比較大的N，性能提高很明顯（接近一半）。另外一個(gè)可改進(jìn)的地方是外層循環(huán)的upto(n)，可以改為upto(Integer(Math.sqrt(n))，其實(shí)這兩個(gè)改動(dòng)效果是重疊的，任意改一個(gè)就差不多了。賦值次數(shù)S應(yīng)為：



結(jié)果為：



可以看到效率的提升是很明顯的，畢竟lnln2³²也才不到3.1，ln2約為0.7。