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

周尚

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

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

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

（一）關于算法的時間復雜度

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

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

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

與此相關的斐波那契字符串的定義如下：

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”的個數，則前n個字符中“1”的個數為S（1，n），簡記為Sn，即前綴和.

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

二、時間復雜度為O（1）的算法

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

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

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

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

三、算法證明

定義：

令fi為斐波那契數列第i項，

Fi為斐波那契數列前i項之和，即∑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為最大分解次數，an為斐波那契字符串前n個字符的最后一位，對于i≠j，i，j∈[1，t]，有Fci≠Fcj.

證明：

根據前述定義及內在關系，可將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進行重復分解，令n-fcn+1=m，則

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

假設經過t次分解后出現S1（an=0）或S2（an=1），分解結束，可得

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φ}，{}表示取小數部分.

引理2：數列{ri}的奇數項單調遞減，偶數項單調遞增，且limi→∞ri=0.

證明：由定義可知，

r0=φ-1，

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

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

ri=ri-1+ri-2.

當i≥2時，用數學歸納法證明ri=（-φ）ri-1.

當i=2時，r2=3φ-2=（-φ）r1，

假設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.

即當i=k時也成立.

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

可見，數列{ri}的奇數項單調遞減，偶數項單調遞增，且limi→∞ri=0，引理2得證.

引理3：數列{Ri}的奇數項單調遞減，偶數項單調遞增，且limi→∞Ri=1-φ.

證明：由引理2可得

φ-1

每一項同時減去（φ-1），得

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

由于Fi=fi+2-1，因此上式可變為

0

因為-fi+1+1是整數，所以

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

即Ri=ri+1-φ.

因此，數列{Ri}的奇偶項單調性同數列{ri}，limi→∞Ri=1-φ，引理3得證.

下面是算法證明.

用第二數學歸納法證明Sn=nφ」.

當k=1時，S1=0=φ」，

當k=2時，S2=1=2φ」，

假設k

當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下標和相等，因此上式可變為

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，對上式進行縮放可得

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

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

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

又因為φ=φ>2φ-1=2φ，

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

因為0≤nφ<1，所以0≤nφ」-Sn<1.

因為nφ」，Sn皆為整數，所以nφ」-Sn=0，

即Sn=nφ」.

算法得證.

四、相關推論

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

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

4.3任取n，前n項的平均數Snn=nφ」n<φ，且limn→∞Snn=φ.

4.4任取n，數列{ai}前n項的方差σ2n小于2φ-1，且趨于2φ-1.

證明：

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

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

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

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

4.5附件：時間復雜度為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;

}