Application of Fuzzy Quasi-Metric in Complexity Analysis

在本文中，符号${{\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]介绍的概率拟度量(P_C，∧)可看作一个特殊的模糊拟度量.

注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上的一个模糊拟度量. 此外，若Mⁱ是X×X×[0，∞)上的函数，且满足Mⁱ(x，y，t)=min{M(x，y，t)，M^-1(x，y，t)}，则(Mⁱ，*)是X上的一个模糊度量.

文献[10]证明了：X上任意的模糊度量Mⁱ可以诱导生成一个T₀拓扑τ_Mⁱ，该拓扑有一个开球族$\left\{B_{M^{i}}\left(x, \frac{1}{n}, \frac{1}{n}\right): n \in \mathbb{N}_{+}\right\}$的局部基，其中

此外τ_Mⁱ是T₂分离的和第一可数的.

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

定义4  设(X，M，*)是一个模糊拟度量空间，若对X中任意的左K-柯西列{x_n}，存在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)是一个拟度量空间，M_d是定义在X×X×[0，∞)上的函数，且对任意的x，y∈X，t≥0，有

若*为任意的连续t-模，则(M_d，*)为X上的一个模糊拟度量，称(M_d，*)是由d导出的标准模糊拟度量.

接下来我们介绍拟度量空间的一些基本概念.

定义5^[13]  设(X，d)是一个拟度量空间，若对∀ε∈(0，1)，t＞0，都存在n₀∈${{\mathbb{N}}_{+}}$，当m≥n≥n₀时d(x_n，x_m)＜ε，则称序列{x_n}为左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为复杂性函数集，称d_C为复杂性拟度量，称(C，d_C)为复杂性(拟度量)空间.

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

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

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

设f，g∈C，若对∀n∈${{\mathbb{N}}_{+}}$有f(n)≤g(n)，则称f的所有输入效率都优于g. 显然地，若f的所有输入效率都优于g，则d_C(f，g)=0.

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

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

例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. 此时，显然d_C(f，g)≠0. 因此，复杂性拟度量d_C不适合刻画算法的渐近效率.

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

定义8^[9]  对∀f，g∈C，t＞0，定义辅助函数Q_C

其中t∈(n，n+1]，n∈${{\mathbb{N}}_{+}}$.

性质1^[9]  对∀f，g∈C，t∈(0，1]，有Q_C(f，g，t)=d_C(f，g).

性质2^[9]  对∀f，g，h∈C，t，s＞0，有Q_C(f，g，t+s)≤Q_C(f，h，t)+Q_C(h，g，s).

性质3^[9]  对∀f，g∈C，函数Q_C(f，g，·)在(0，∞)上是非增的和左连续的.

定理2  设C是复杂性函数集，*是连续t-模，f，g∈C，在C×C×[0，∞)上定义函数M_C，

则

(ⅰ) (M_C，*)是C上的一个模糊拟度量；

(ⅱ) 若(M_dC，*)是由d_C导出的标准模糊拟度量，则对∀t∈(0，1]，M_C(f，g，t)=M_dC(f，g，t).

证  (ⅰ) (FQM1)显然成立.

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

反之，若对∀t＞0，

则特别地当t=1时，

因此

又由性质1即得

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

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

即

又因为

故

即证得

因此

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

(ⅱ) 由性质1，对∀f，g∈C，当t∈(0，1]时， Q_C(f，g，t)=d_C(f，g)，于是M_C(f，g，t)=M_dC(f，g，t).

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

定理3  在模糊拟度量空间(C，M_C，*)中，对∀f，g∈C，f的渐近效率优于g当且仅当存在n₀∈${{\mathbb{N}}_{+}}$，使得对∀t＞n₀，有M_C(f，g，t)=1.

证  必要性对∀f，g∈C，若f的渐近效率优于g，则存在n₀∈${{\mathbb{N}}_{+}}$，使得对∀n≥n₀有f(n)≤g(n). 由Q_C(f，g，t)的定义可得，对任意的t＞n₀，Q_C(f，g，t)=0，即M_C(f，g，t)=1.

充分性 由条件，当t∈(n₀，n₀+1]时，M_C(f，g，t)=1，即Q_C(f，g，t)=0. 于是，对∀n≥n₀，有f(n)≤g(n)，即f的渐近效率优于g.

例3表明模糊拟度量M_C可以刻画算法的渐近效率.

例3  令f(n)，g(n)为例2中的函数. 经计算得：当n=0，1，2，…，10时f(n)＞g(n)；当n≥11时f(n)＜g(n). 因此，取n₀=11，则对∀t∈(11，12]，Q_C(f，g，t)=0. 由性质3可知函数Q_C(f，g，·)是非增的，所以对∀t＞11，Q_C(f，g，t)=0，即M_C(f，g，t)=1. 因此f的渐近效率优于g. 即模糊拟度量M_C可以刻画算法的渐近效率.

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

证  令{f_n}是(C，M_C，*)中的左K-柯西列，取$\varepsilon \in\left(0, \frac{1}{2}\right)$，则存在n₀∈${{\mathbb{N}}_{+}}$，使得当m≥n≥n₀时，M_C(f_n，f_m，t)＞1-ε. 由定理2得M_C(f_n，f_m，1)=M_dC(f_n，f_m，1). 所以当m≥n≥n₀时，

即

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

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

即

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

本节主要介绍模糊拟度量空间(C，M_C，*)的不动点定理及其应用.

定义9  设Φ是模糊拟度量空间(C，M_C，*)上的一个自映射，对于f，g∈C，t∈(0，1]，若存在k∈(0，1)，使得

则称自映射Φ是(0，1]-压缩的.

定理5  若Φ是一个(0，1]-压缩的自映射，则Φ有唯一的不动点.

证  令Φf_n=f_n+1，则存在k∈(0，1)，使得对∀n∈${{\mathbb{N}}_{+}}$，t∈(0，1]，总有

则

由性质1可得

根据三角不等式得，对∀n，m∈${{\mathbb{N}}_{+}}$有

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

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

因此，{f_n}在模糊度量M_Cⁱ意义下收敛到p. 由Φ是(0，1]-压缩映射可得，对∀t∈(0，1]，

因此，{f_n}在模糊度量M_Cⁱ意义下收敛到Φp. 又因为模糊度量M_Cⁱ的拓扑是T₂分离的，所以p=Φp，即Φ有不动点p.

下面证Φ的不动点的唯一性. 令q∈C是Φ的不动点，则对∀t∈(0，1]，M_C(p，q，t)=M_C(Φp，Φq，t). 由于Φ是(0，1]-压缩的，因此存在k∈(0，1)，使得对∀t∈(0，1]，

即M_C(p，q，t)=1. 因为M_C(p，q，·)是递增的，所以对∀t＞0，都有M_C(p，q，t)=1. 同理可得，对∀t＞0，都有M_C(q，p，t)=1. 因此p=q. 即Φ的不动点是唯一的.

接下来我们将应用定理5来证明与分治算法相关的递归方程的解的存在唯一性.

正如文献[1, 14]中所述，分治算法都是通过递归的方法将原始问题分解成几个子问题来解决，每个子问题都是由相同的算法单独解决的，然后组合后的结果就是原始问题的答案. 因此，分治算法的复杂性通常由下面的递归方程的解来表示：

其中，n∈{b^p：p∈${{\mathbb{N}}_{+}}$}，并且h(n)＜+∞. 递归方程(1)自然地诱导出一个映射Φ，定义如下：

文献[1]证明了：对∀f，g∈C，当k=$\frac{1}{a}$时，d_C(Φf，Φg)≤kd_C(f，g). 由性质1可得，对∀t∈(0，1]，

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

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

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

正如文献[16]中所述，递归方程(2)可以自然地诱导出一个映射Φ：C→C，定义如下：

由文献[17]可知，对∀f，g∈C，d_C(Φf，Φg)≤$\frac{d_{C}(f, g)}{2}$. 取k=$\frac{1}{2}$，由性质1得，对∀t∈(0，1]，

因此，Φ是一个(0，1]-压缩的自映射. 应用定理5可得，Φ有唯一的不动点g₀∈C. 从而，若定义函数h：${{\mathbb{N}}_{+}}$→[0，+∞)如下：

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