网站首页  词典首页

请输入您要查询的论文:

 

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

    }

随便看

 

科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

 

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间:2025/3/14 7:40:00