斐波那契字符串前缀和的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;

}