模糊拟度量在复杂性分析中的应用

田恪明，吴健荣

1. 苏州科技大学 数学科学学院，江苏 苏州 215009； 2. 苏州科技大学 天平学院 公共教学部，江苏 苏州 215009

文献[1]为了构建复杂性分析的拓扑基础，在复杂性空间中引入了一种拟度量，并将其应用于分治算法的效率分析中．随后，文献[2]进一步研究了该拟度量空间的性质，证明了复杂性空间是Smyth完备的，可以被建模为拟范数半线性空间．关于此空间的更多结果详见文献[3-6].

算法的渐近效率在复杂性分析中具有重要的应用．然而，正如本文例2所述，文献[1]中引入的拟度量并不适合刻画算法的渐近效率.

为解决上述问题，在本文中，我们在复杂性函数集上引入了一种模糊拟度量，并且证明了它可以刻画算法的渐近效率．此外，我们建立了一个不动点定理，并应用此定理证明了与分治算法和快速排序算法相关的递归方程解的存在性和唯一性.

1 预备知识

在本文中，符号N+表示非负整数集.

(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⟺x=y；

(FQM3) ∀t，s≥0，M(x，z，t+s)≥M(x，y，t)*M(y，z，s)；

则称(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上的一个模糊度量.

此外τMi是T2分离的和第一可数的.

定义3[8]设{xn}是模糊拟度量空间(X，M，*)中的序列，若对∀ε∈(0，1)，t>0，都存在n0∈N+，使得当m≥n≥n0时M(xn，xm，t)>1-ε，则称序列{xn}是左K-柯西列.

例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∈N+，当m≥n≥n0时d(xn，xm)<ε，则称序列{xn}为左K-柯西列.

定义6[13]设(X，d)是一个拟度量空间，若(X，d)中任意的左K-柯西列是收敛的，则称(X，d)是Smyth完备的.

则称C为复杂性函数集，称dC为复杂性拟度量，称(C，dC)为复杂性(拟度量)空间.

注4容易验证dC是C上的一个拟度量.

文献[2]证明了复杂性空间(C，dC)是Smyth完备的.

在复杂性理论中，算法的复杂性由它的运行时间函数f(n)(n∈N+)来表示，其中f(n)被称为算法的复杂性函数.

设f，g∈C，若对∀n∈N+有f(n)≤g(n)，则称f的所有输入效率都优于g．显然地，若f的所有输入效率都优于g，则dC(f，g)=0.

在本文中，设f，g∈C，若存在n0∈N+，使得对所有的n≥n0都有f(n)≤g(n)，我们称f的渐近效率优于g.

例2说明复杂性拟度量dC不适合刻画算法的渐近效率.

2 复杂性函数集上的模糊拟度量空间

本节将在复杂性函数集C上引入模糊拟度量，以此刻画算法的渐近效率.

定义8[9]对∀f，g∈C，t>0，定义辅助函数QC

其中t∈(n，n+1]，n∈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，

则

证(FQM1)显然成立.

(FQM2) 令f，g∈C，对∀t>0，当f=g时，

反之，若对∀t>0，

MC(f，g，t)=MC(g，f，t)=1

则特别地当t=1时，

MC(f，g，1)=MC(g，f，1)=1

因此

QC(f，g，1)=QC(g，f，1)=0

又由性质1即得

dC(f，g)=dC(g，f)=0

因为dC是C上的拟度量，所以f=g.

(FQM3) 令f，g，h∈C，对∀t，s≥0，不妨设MC(f，h，t)≤MC(g，h，s)，所以

即

tQC(h，g，s)≤sQC(f，h，t)

又因为

tQC(f，g，t+s)≤tQC(f，h，t)+tQC(h，g，s)≤(t+s)QC(f，h，t)

故

即证得

MC(f，g，t+s)≥MC(f，h，t)∧MC(h，g，s)

因此

MC(f，g，t+s)≥MC(f，h，t)*MC(h，g，s)

(FQM4) 由性质3可知，显然成立.

下文中的模糊拟度量空间(C，MC，*)均为定理2中引入的模糊拟度量空间.

定理3在模糊拟度量空间(C，MC，*)中，对∀f，g∈C，f的渐近效率优于g当且仅当存在n0∈N+，使得对∀t>n0，有MC(f，g，t)=1.

证必要性 对∀f，g∈C，若f的渐近效率优于g，则存在n0∈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)11，QC(f，g，t)=0，即MC(f，g，t)=1．因此f的渐近效率优于g．即模糊拟度量MC可以刻画算法的渐近效率.

定理4模糊拟度量空间(C，MC，*)是Smyth完备的.

即

因此，{fn}是(C，dC)中的左K-柯西列．因为(C，dC)是Smyth完备的，所以存在f∈C，使得

又由性质1可得，对∀t>0都有

即

所以左K-柯西列{fn}是收敛的．因此，(C，MC，*)是Smyth完备的.

3 不动点定理及其应用

本节主要介绍模糊拟度量空间(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∈N+，t∈(0，1]，总有

则

QC(fn+1，fn+2，t)≤kQC(fn，fn+1，t)

由性质1可得

dC(fn+1，fn+2)≤kdC(fn，fn+1)

根据三角不等式得，对∀n，m∈N+有

所以{fn}在(C，dC)中是一个左K-柯西列．因为(C，dC)是Smyth完备的，从而{fn}在度量(dC)s意义下是收敛的．因此，序列{fn}在模糊度量(MdC)i意义下是收敛的．即存在p∈C，对∀t∈(0，1]，有

又由定理2可得，对∀t∈(0，1]，

下面证Φ的不动点的唯一性．令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]中所述，分治算法都是通过递归的方法将原始问题分解成几个子问题来解决，每个子问题都是由相同的算法单独解决的，然后组合后的结果就是原始问题的答案．因此，分治算法的复杂性通常由下面的递归方程的解来表示：

(1)

其中，n∈{bp：p∈N+}，并且h(n)<+∞．递归方程(1)自然地诱导出一个映射Φ，定义如下：

因此，Φ是一个(0，1]-压缩的自映射．应用定理5可得，Φ有唯一的不动点g0∈C，即为递归方程(1)的解.

最后我们将应用定理5来证明与快速排序算法相关的递归方程解的存在唯一性.

文献[15]在讨论快速排序算法的平均案例分析时得出了一个递归方程T：

(2)

则h就是递归方程(2)的唯一解.