斐波那契字符串前綴和的O(1)算法及其證明

周尚

【摘要】作者在編寫斐波那契字符串前綴和算法程序過程中，通過具體觀察、抽象思維和程序驗(yàn)證等方式，結(jié)合斐波那契數(shù)列特點(diǎn)，提出了一種簡單而奇妙的算法，即Sn=nφ」，」表示取整，φ為黃金分割比5-12，將計算的時間復(fù)雜度從O（lg2n）降為O（1），運(yùn)用數(shù)學(xué)歸納法予以證明，并得出了任意一段字符串的求和公式、任意一個字符是“0”或“1”的計算公式等相關(guān)推論.

【關(guān)鍵詞】斐波那契字符串;前綴和;O（1）算法

一、斐波那契字符串前綴和常見算法的時間復(fù)雜度

（一）關(guān)于算法的時間復(fù)雜度

一個算法的語句執(zhí)行總次數(shù)T（n）是關(guān)于問題規(guī)模n的函數(shù)，算法的時間復(fù)雜度就是分析T（n）隨n的變化情況，確定T（n）的數(shù)量級，通常記為：T（n）=O（g（n）），其中，g（n）是問題規(guī)模n的某個函數(shù).它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和g（n）的增長率相同.一般地，T（n）關(guān)于n的數(shù)量級越低，算法越優(yōu).

（二）斐波那契字符串前綴和常見算法的時間復(fù)雜度

眾所周知，斐波那契數(shù)列是1，1，2，3，5，8，…，即f1=1，f2=1，fi=fi-1+fi-2，i>2且i∈Z.

與此相關(guān)的斐波那契字符串的定義如下：

f（0）=“0”，f（1）=“1”，f（i）=f（i-2）f（i-1），i>1且i∈Z，

F=f（0）f（1）f（2）…=“01011010110110101101…”，稱為無限斐波那契字符串，其中，雙引號中的0，1均為字符，表示字符串的拼接.

令S（l，r）為無限斐波那契字符串F的第l個字符至第r個字符中“1”的個數(shù)，則前n個字符中“1”的個數(shù)為S（1，n），簡記為Sn，即前綴和.

要求以盡量低的時間復(fù)雜度計算前綴和Sn.目前常見算法的時間復(fù)雜度為O（log2n）.

二、時間復(fù)雜度為O（1）的算法

人們通過具體觀察、抽象思維和程序驗(yàn)證等方式，結(jié)合斐波那契數(shù)列特點(diǎn)，提出并證明了一種時間復(fù)雜度為O（1）的奇妙算法，即Sn=nφ」，」表示取整，φ為黃金分割比5-12.

該算法將計算的時間復(fù)雜度降到最低.以n=16為例，前16個字符“0101101011011010”中有9個“1”，代入公式得

S16=16*（5-1）/2」=9，

得到驗(yàn)證.筆者通過計算機(jī)程序驗(yàn)證n≤1018時的情形均成立，計算程序見附件.

三、算法證明

定義：

令fi為斐波那契數(shù)列第i項(xiàng)，

Fi為斐波那契數(shù)列前i項(xiàng)之和，即∑ij=1fj，

顯然，fi-2+fi-1=fi，fi+2-1=Fi.

令f-i=maxfj

F-i=maxFj

引理1：Sn=∑ti=1（SFci-SFci-2）+S1（an=0），∑ti=1（SFci-SFci-2）+S2（an=1），

t為最大分解次數(shù)，an為斐波那契字符串前n個字符的最后一位，對于i≠j，i，j∈[1，t]，有Fci≠Fcj.

證明：

根據(jù)前述定義及內(nèi)在關(guān)系，可將Sn作如下分解：

Sn=SF-n+S（F-n+1，n）=SFcn+S（Fcn+1，n）=SFcn+S（Fcn-2+1，n-fcn-1-fcn）=SFcn+S（Fcn-2+1，n-fcn+1）=SFcn+Sn-fcn+1-SFcn-2=Sn-fcn+1+（SFcn-SFcn-2），（1）

對（1）式中Sn-fcn+1進(jìn)行重復(fù)分解，令n-fcn+1=m，則

Sn-fcn+1=Sm=Sm-fcm+1+（SFcm-SFcm-2）.

假設(shè)經(jīng)過t次分解后出現(xiàn)S1（an=0）或S2（an=1），分解結(jié)束，可得

Sn=∑ti=1（SFci-SFci-2）+S1（an=0），∑ti=1（SFci-SFci-2）+S2（an=1），

顯然，對于i≠j，i，j∈[1，t]，有Fci≠Fcj.

引理1得證.

定義：令ri=fi+2φ-fi+1，Ri={Fiφ}，{}表示取小數(shù)部分.

引理2：數(shù)列{ri}的奇數(shù)項(xiàng)單調(diào)遞減，偶數(shù)項(xiàng)單調(diào)遞增，且limi→∞r(nóng)i=0.

證明：由定義可知，

r0=φ-1，

r1=f3φ-f2=2φ-1，

r2=f4φ-f3=3φ-2，

ri=ri-1+ri-2.

當(dāng)i≥2時，用數(shù)學(xué)歸納法證明ri=（-φ）ri-1.

當(dāng)i=2時，r2=3φ-2=（-φ）r1，

假設(shè)i=k-1時，rk-1=（-φ）rk-2成立，則

rk=rk-1+rk-2=（-φ）rk-2+rk-2=（1-φ）rk-2=φ2rk-2=（-φ）（-φ）rk-2=（-φ）rk-1.

即當(dāng)i=k時也成立.

由此可知，ri=（-φ）i（φ-1）.

可見，數(shù)列{ri}的奇數(shù)項(xiàng)單調(diào)遞減，偶數(shù)項(xiàng)單調(diào)遞增，且limi→∞r(nóng)i=0，引理2得證.

引理3：數(shù)列{Ri}的奇數(shù)項(xiàng)單調(diào)遞減，偶數(shù)項(xiàng)單調(diào)遞增，且limi→∞Ri=1-φ.

證明：由引理2可得

φ-1

每一項(xiàng)同時減去（φ-1），得

0<（fi+2-1）φ-fi+1+1<1，

由于Fi=fi+2-1，因此上式可變?yōu)?/p>

0

因?yàn)?fi+1+1是整數(shù)，所以

Fiφ=Fiφ-fi+1+1=（fi+2-1）φ-fi+1+1=fi+2φ-fi+1+1-φ，

即Ri=ri+1-φ.

因此，數(shù)列{Ri}的奇偶項(xiàng)單調(diào)性同數(shù)列{ri}，limi→∞Ri=1-φ，引理3得證.

下面是算法證明.

用第二數(shù)學(xué)歸納法證明Sn=nφ」.

當(dāng)k=1時，S1=0=φ」，

當(dāng)k=2時，S2=1=2φ」，

假設(shè)k

當(dāng)k=n時，由引理1可知，

nφ」-Sn=nφ」-（∑ti=1（SFci-SFci-2）+S1orS2）

=nφ」-（∑ti=1（Fciφ」-Fci-2φ」）

+φ」or2φ」）=nφ-nφ-（∑ti=1（Fciφ-Fci-2φ）

+φor2φ-∑ti=1（Fciφ-Fci-2φ）

-φor2φ）.

由于分解過程中每次拆分出的S下標(biāo)和相等，因此上式可變?yōu)?/p>

nφ」-Sn=nφ-nφ-（nφ-∑ti=1（Fciφ

-Fci-2φ）-φor2φ）=-nφ+（∑ti=1（Fciφ-Fci-2φ）

+φor2φ）=-nφ+（∑ti=1（Rci-Rci-2）

+φor2φ）.

利用引理3，對上式進(jìn)行縮放可得

∑ti=1（Rci-Rci-2）<∑∞ci為偶數(shù)且ci≥2（Rci-Rci-2）

∑ti=1（Rci-Rci-2）>∑∞ci為奇數(shù)且ci≥3（Rci-Rci-2）>limi→∞Ri-R1=1-2φ，

即1-2φ<∑ti=1（Rci-Rci-2）<1-φ.

又因?yàn)棣?φ>2φ-1=2φ，

所以0<∑ti=1（Rci-Rci-2）+φor2φ<1.

因?yàn)?≤nφ<1，所以0≤nφ」-Sn<1.

因?yàn)閚φ」，Sn皆為整數(shù)，所以nφ」-Sn=0，

即Sn=nφ」.

算法得證.

四、相關(guān)推論

4.1斐波那契字符串第l個字符至第r個字符中“1”的個數(shù)為S（l，r）=Sr-Sl-1=rφ」-（l-1）φ」.

4.2斐波那契字符串中第n個字符an，當(dāng)l=r=n時，an=S（n，n）=Sn-Sn-1=nφ」-（n-1）φ」.

4.3任取n，前n項(xiàng)的平均數(shù)Snn=nφ」n<φ，且limn→∞Snn=φ.

4.4任取n，數(shù)列{ai}前n項(xiàng)的方差σ2n小于2φ-1，且趨于2φ-1.

證明：

σ2n=∑ni=1ai-Snn2n=∑ni=1a2i-2Snn∑ni=1ai+nSnn2n，

由于ai=0或1，且前n項(xiàng)中有Sn個1，所以上式可化為

σ2n=∑ni=1a2i-2Snn∑ni=1ai+nSnn2n=Sn-2SnnSn+S2nnn=Sn-S2nnn=Snn-Snn2，

limn→∞σ2n=φ-φ2=2φ-1.

4.5附件：時間復(fù)雜度為O（1）的算法程序

#include

usingnamespacestd;

constlonglongG[3]={61803398，87498948，48204587}，P=1e8;

longlongn，f[3]，A[5];

intmain（）

{

cin>>n;

f[0]=n/P/P，f[1]=n/P%P，f[2]=n%P;

for（inti=0;i<3;i++）

for（intj=0;j<3;j++）

A[i+j]+=f[i]*G[j];

for（inti=4;i>0;i--）

A[i-1]+=A[i]/P，A[i]%=P;

cout<

return0;

}