模糊擬度量在復雜性分析中的應用

田恪明，吳健榮

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)的唯一解.