DC3后缀数组复杂度N证明
已知复杂度公式为T(N)=T(2/3N)+O(N)假设N为1，但无穷递进，则可以得到
1+2/3+4/9+8/27....
其中为等比数列2/3
利用等比数列公式
其中n为项数，r为等比数列2/3
当n逼近正无穷时则r的n次方无穷小
则1-r的n次方无穷接近于1，则忽略不计
得到Sn=a/(1-r)
其中a为1
则得到了Sn=1/(1-2/3)
得到了Sn=1/（1/3）
可得复杂度极限为3N，约去常数项
DC3的复杂度为N
页:
[1]