-
开放科学(资源服务)标志码(OSID):
-
文献[1]为了构建复杂性分析的拓扑基础,在复杂性空间中引入了一种拟度量,并将其应用于分治算法的效率分析中. 随后,文献[2]进一步研究了该拟度量空间的性质,证明了复杂性空间是Smyth完备的,可以被建模为拟范数半线性空间. 关于此空间的更多结果详见文献[3-6].
算法的渐近效率在复杂性分析中具有重要的应用. 然而,正如本文例2所述,文献[1]中引入的拟度量并不适合刻画算法的渐近效率.
为解决上述问题,在本文中,我们在复杂性函数集上引入了一种模糊拟度量,并且证明了它可以刻画算法的渐近效率. 此外,我们建立了一个不动点定理,并应用此定理证明了与分治算法和快速排序算法相关的递归方程解的存在性和唯一性.
全文HTML
-
在本文中,符号
${{\mathbb{N}}_{+}}$ 表示非负整数集.定义1[7] 设*:[0, 1]×[0, 1]→[0, 1]是一个二元运算,如果
(a) *满足结合律和交换律;
(b) *是连续的;
(c) ∀a∈[0, 1],a*1=a;
(d) 当a≤c和b≤d(a,b,c,d∈[0, 1])时,a*b≤c*d.
则称*是一个连续t-模.
注1 当a,b∈[0, 1]时,对任意的连续t-模*,a∧b≥a*b恒成立.
定义2[8] 设X是一个非空集合,*是一个连续t-模,M是X×X×[0,∞)上的模糊集,对∀x,y,z∈X,有
(FQM1) M(x,y,0)=0;
(FQM2) ∀t>0,M(x,y,t)=M(y,x,t)=1
$\Leftrightarrow $ x=y;(FQM3) ∀t,s≥0,M(x,z,t+s)≥M(x,y,t)*M(y,z,s);
(FQM4) M(x,y,·):[0,∞)→[0, 1]是左连续的.
则称(M,*)为X上的一个模糊拟度量.
注2 文献[9]介绍的概率拟度量(PC,∧)可看作一个特殊的模糊拟度量.
注3若M还满足
(FQM5) ∀t>0,M(x,y,t)=M(y,x,t).
则(M,*)为文献[10]意义下的一个模糊度量,有关模糊度量的更多结果详见文献[11-12].
设(M,*)是X上的模糊拟度量,若M-1是X×X×[0,∞)上的函数,且满足M-1(x,y,t)=M(y,x,t),则(M-1,*)也是X上的一个模糊拟度量. 此外,若Mi是X×X×[0,∞)上的函数,且满足Mi(x,y,t)=min{M(x,y,t),M-1(x,y,t)},则(Mi,*)是X上的一个模糊度量.
文献[10]证明了:X上任意的模糊度量Mi可以诱导生成一个T0拓扑τMi,该拓扑有一个开球族
$\left\{B_{M^{i}}\left(x, \frac{1}{n}, \frac{1}{n}\right): n \in \mathbb{N}_{+}\right\}$ 的局部基,其中此外τMi是T2分离的和第一可数的.
定义3[8] 设{xn}是模糊拟度量空间(X,M,*)中的序列,若对∀ε∈(0,1),t>0,都存在n0∈
${{\mathbb{N}}_{+}}$ ,使得当m≥n≥n0时M(xn,xm,t)>1-ε,则称序列{xn}是左K-柯西列.定义4 设(X,M,*)是一个模糊拟度量空间,若对X中任意的左K-柯西列{xn},存在x∈X,使得
$\lim\limits _{n \rightarrow \infty} M\left(x, x_{n}, t\right)=\lim \limits_{n \rightarrow \infty} M\left(x_{n}, x, t\right)=1$ ,则称(X,M,*)是Smyth完备的.例1[8] 设(X,d)是一个拟度量空间,Md是定义在X×X×[0,∞)上的函数,且对任意的x,y∈X,t≥0,有
若*为任意的连续t-模,则(Md,*)为X上的一个模糊拟度量,称(Md,*)是由d导出的标准模糊拟度量.
接下来我们介绍拟度量空间的一些基本概念.
定义5[13] 设(X,d)是一个拟度量空间,若对∀ε∈(0,1),t>0,都存在n0∈
${{\mathbb{N}}_{+}}$ ,当m≥n≥n0时d(xn,xm)<ε,则称序列{xn}为左K-柯西列.定义6[13] 设(X,d)是一个拟度量空间,若(X,d)中任意的左K-柯西列是收敛的,则称(X,d)是Smyth完备的.
定理1[2] 设(X,d)是一个拟度量空间,(X,d)是Smyth完备的当且仅当(X,d)中任意的左K-柯西列是收敛的,即存在x∈X使得
$\lim \limits_{n \rightarrow \infty} d^{s}\left(x, x_{n}\right)=0$ .定义7[1] 设
$C=\left\{f: \mathbb{N}_{+} \longrightarrow(0,+\infty]: \sum\limits_{n=1}^{+\infty} 2^{-n} \frac{1}{f(n)} <+\infty\right\} $ ,对∀f,g∈C,定义则称C为复杂性函数集,称dC为复杂性拟度量,称(C,dC)为复杂性(拟度量)空间.
注4 容易验证dC是C上的一个拟度量.
文献[2]证明了复杂性空间(C,dC)是Smyth完备的.
在复杂性理论中,算法的复杂性由它的运行时间函数f(n)(n∈
${{\mathbb{N}}_{+}}$ )来表示,其中f(n)被称为算法的复杂性函数.设f,g∈C,若对∀n∈
${{\mathbb{N}}_{+}}$ 有f(n)≤g(n),则称f的所有输入效率都优于g. 显然地,若f的所有输入效率都优于g,则dC(f,g)=0.在本文中,设f,g∈C,若存在n0∈
${{\mathbb{N}}_{+}}$ ,使得对所有的n≥n0都有f(n)≤g(n),我们称f的渐近效率优于g.例2说明复杂性拟度量dC不适合刻画算法的渐近效率.
例2 设f,g∈C,对任意的n∈
${{\mathbb{N}}_{+}}$ ,f(n)=n+1,g(n)=$\frac{2^{n}}{n^{2}+2}$ . 通过计算可得:当n=0,1,2,…,10时f(n)>g(n);当n≥11时f(n)<g(n). 因此,f的渐近效率优于g. 此时,显然dC(f,g)≠0. 因此,复杂性拟度量dC不适合刻画算法的渐近效率.
-
本节将在复杂性函数集C上引入模糊拟度量,以此刻画算法的渐近效率.
定义8[9] 对∀f,g∈C,t>0,定义辅助函数QC
其中t∈(n,n+1],n∈
${{\mathbb{N}}_{+}}$ .性质1[9] 对∀f,g∈C,t∈(0,1],有QC(f,g,t)=dC(f,g).
性质2[9] 对∀f,g,h∈C,t,s>0,有QC(f,g,t+s)≤QC(f,h,t)+QC(h,g,s).
性质3[9] 对∀f,g∈C,函数QC(f,g,·)在(0,∞)上是非增的和左连续的.
定理2 设C是复杂性函数集,*是连续t-模,f,g∈C,在C×C×[0,∞)上定义函数MC,
则
(ⅰ) (MC,*)是C上的一个模糊拟度量;
(ⅱ) 若(MdC,*)是由dC导出的标准模糊拟度量,则对∀t∈(0,1],MC(f,g,t)=MdC(f,g,t).
证 (ⅰ) (FQM1)显然成立.
(FQM2) 令f,g∈C,对∀t>0,当f=g时,
反之,若对∀t>0,
则特别地当t=1时,
因此
又由性质1即得
因为dC是C上的拟度量,所以f=g.
(FQM3) 令f,g,h∈C,对∀t,s≥0,不妨设MC(f,h,t)≤MC(g,h,s),所以
即
又因为
故
即证得
因此
(FQM4) 由性质3可知,显然成立.
(ⅱ) 由性质1,对∀f,g∈C,当t∈(0,1]时, QC(f,g,t)=dC(f,g),于是MC(f,g,t)=MdC(f,g,t).
下文中的模糊拟度量空间(C,MC,*)均为定理2中引入的模糊拟度量空间.
定理3 在模糊拟度量空间(C,MC,*)中,对∀f,g∈C,f的渐近效率优于g当且仅当存在n0∈
${{\mathbb{N}}_{+}}$ ,使得对∀t>n0,有MC(f,g,t)=1.证 必要性对∀f,g∈C,若f的渐近效率优于g,则存在n0∈
${{\mathbb{N}}_{+}}$ ,使得对∀n≥n0有f(n)≤g(n). 由QC(f,g,t)的定义可得,对任意的t>n0,QC(f,g,t)=0,即MC(f,g,t)=1.充分性 由条件,当t∈(n0,n0+1]时,MC(f,g,t)=1,即QC(f,g,t)=0. 于是,对∀n≥n0,有f(n)≤g(n),即f的渐近效率优于g.
例3表明模糊拟度量MC可以刻画算法的渐近效率.
例3 令f(n),g(n)为例2中的函数. 经计算得:当n=0,1,2,…,10时f(n)>g(n);当n≥11时f(n)<g(n). 因此,取n0=11,则对∀t∈(11,12],QC(f,g,t)=0. 由性质3可知函数QC(f,g,·)是非增的,所以对∀t>11,QC(f,g,t)=0,即MC(f,g,t)=1. 因此f的渐近效率优于g. 即模糊拟度量MC可以刻画算法的渐近效率.
定理4 模糊拟度量空间(C,MC,*)是Smyth完备的.
证 令{fn}是(C,MC,*)中的左K-柯西列,取
$\varepsilon \in\left(0, \frac{1}{2}\right)$ ,则存在n0∈${{\mathbb{N}}_{+}}$ ,使得当m≥n≥n0时,MC(fn,fm,t)>1-ε. 由定理2得MC(fn,fm,1)=MdC(fn,fm,1). 所以当m≥n≥n0时,即
因此,{fn}是(C,dC)中的左K-柯西列. 因为(C,dC)是Smyth完备的,所以存在f∈C,使得
又由性质1可得,对∀t>0都有
即
所以左K-柯西列{fn}是收敛的. 因此,(C,MC,*)是Smyth完备的.
-
本节主要介绍模糊拟度量空间(C,MC,*)的不动点定理及其应用.
定义9 设Φ是模糊拟度量空间(C,MC,*)上的一个自映射,对于f,g∈C,t∈(0,1],若存在k∈(0,1),使得
则称自映射Φ是(0,1]-压缩的.
定理5 若Φ是一个(0,1]-压缩的自映射,则Φ有唯一的不动点.
证 令Φfn=fn+1,则存在k∈(0,1),使得对∀n∈
${{\mathbb{N}}_{+}}$ ,t∈(0,1],总有则
由性质1可得
根据三角不等式得,对∀n,m∈
${{\mathbb{N}}_{+}}$ 有所以{fn}在(C,dC)中是一个左K-柯西列. 因为(C,dC)是Smyth完备的,从而{fn}在度量(dC)s意义下是收敛的. 因此,序列{fn}在模糊度量(MdC)i意义下是收敛的. 即存在p∈C,对∀t∈(0,1],有
又由定理2可得,对∀t∈(0,1],
因此,{fn}在模糊度量MCi意义下收敛到p. 由Φ是(0,1]-压缩映射可得,对∀t∈(0,1],
因此,{fn}在模糊度量MCi意义下收敛到Φp. 又因为模糊度量MCi的拓扑是T2分离的,所以p=Φp,即Φ有不动点p.
下面证Φ的不动点的唯一性. 令q∈C是Φ的不动点,则对∀t∈(0,1],MC(p,q,t)=MC(Φp,Φq,t). 由于Φ是(0,1]-压缩的,因此存在k∈(0,1),使得对∀t∈(0,1],
即MC(p,q,t)=1. 因为MC(p,q,·)是递增的,所以对∀t>0,都有MC(p,q,t)=1. 同理可得,对∀t>0,都有MC(q,p,t)=1. 因此p=q. 即Φ的不动点是唯一的.
接下来我们将应用定理5来证明与分治算法相关的递归方程的解的存在唯一性.
正如文献[1, 14]中所述,分治算法都是通过递归的方法将原始问题分解成几个子问题来解决,每个子问题都是由相同的算法单独解决的,然后组合后的结果就是原始问题的答案. 因此,分治算法的复杂性通常由下面的递归方程的解来表示:
其中,n∈{bp:p∈
${{\mathbb{N}}_{+}}$ },并且h(n)<+∞. 递归方程(1)自然地诱导出一个映射Φ,定义如下:文献[1]证明了:对∀f,g∈C,当k=
$\frac{1}{a}$ 时,dC(Φf,Φg)≤kdC(f,g). 由性质1可得,对∀t∈(0,1],因此,Φ是一个(0,1]-压缩的自映射. 应用定理5可得,Φ有唯一的不动点g0∈C,即为递归方程(1)的解.
最后我们将应用定理5来证明与快速排序算法相关的递归方程解的存在唯一性.
文献[15]在讨论快速排序算法的平均案例分析时得出了一个递归方程T:
正如文献[16]中所述,递归方程(2)可以自然地诱导出一个映射Φ:C→C,定义如下:
由文献[17]可知,对∀f,g∈C,dC(Φf,Φg)≤
$\frac{d_{C}(f, g)}{2}$ . 取k=$\frac{1}{2}$ ,由性质1得,对∀t∈(0,1],因此,Φ是一个(0,1]-压缩的自映射. 应用定理5可得,Φ有唯一的不动点g0∈C. 从而,若定义函数h:
${{\mathbb{N}}_{+}}$ →[0,+∞)如下:则h就是递归方程(2)的唯一解.