田恪明，吴健荣

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……