模糊擬度量在復(fù)雜性分析中的應(yīng)用

田恪明，吳健榮

1. 蘇州科技大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，江蘇 蘇州 215009； 2. 蘇州科技大學(xué) 天平學(xué)院 公共教學(xué)部，江蘇 蘇州 215009

文獻[1]為了構(gòu)建復(fù)雜性分析的拓?fù)浠A(chǔ)，在復(fù)雜性空間中引入了一種擬度量，并將其應(yīng)用于分治算法的效率分析中．隨后，文獻[2]進一步研究了該擬度量空間的性質(zhì)，證明了復(fù)雜性空間是Smyth完備的，可以被建模為擬范數(shù)半線性空間．關(guān)于此空間的更多結(jié)果詳見文獻[3-6].

算法的漸近效率在復(fù)雜性分析中具有重要的應(yīng)用．然而，正如本文例2所述，文獻[1]中引入的擬度量并不適合刻畫算法的漸近效率.

為解決上述問題，在本文中，我們在復(fù)雜性函數(shù)集上引入了一種模糊擬度量，并且證明了它可以刻畫算法的漸近效率．此外，我們建立了一個不動點定理，并應(yīng)用此定理證明了與分治算法和快速排序算法相關(guān)的遞歸方程解的存在性和唯一性.

1 預(yù)備知識

在本文中，符號N+表示非負(fù)整數(shù)集.

(a) *滿足結(jié)合律和交換律；

(b) *是連續(xù)的；

(c) ?a∈[0，1]，a*1=a；

(d) 當(dāng)a≤c和b≤d(a，b，c，d∈[0，1])時，a*b≤c*d.

則稱*是一個連續(xù)t-模.

注1當(dāng)a，b∈[0，1]時，對任意的連續(xù)t-模*，a∧b≥a*b恒成立.

定義2[8]設(shè)X是一個非空集合，*是一個連續(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]意義下的一個模糊度量，有關(guān)模糊度量的更多結(jié)果詳見文獻[11-12].

設(shè)(M，*)是X上的模糊擬度量，若M-1是X×X×[0，∞)上的函數(shù)，且滿足M-1(x，y，t)=M(y，x，t)，則(M-1，*)也是X上的一個模糊擬度量．此外，若Mi是X×X×[0，∞)上的函數(shù)，且滿足Mi(x，y，t)=min{M(x，y，t)，M-1(x，y，t)}，則(Mi，*)是X上的一個模糊度量.

此外τMi是T2分離的和第一可數(shù)的.

定義3[8]設(shè){xn}是模糊擬度量空間(X，M，*)中的序列，若對?ε∈(0，1)，t>0，都存在n0∈N+，使得當(dāng)m≥n≥n0時M(xn，xm，t)>1-ε，則稱序列{xn}是左K-柯西列.

例1[8]設(shè)(X，d)是一個擬度量空間，Md是定義在X×X×[0，∞)上的函數(shù)，且對任意的x，y∈X，t≥0，有

若*為任意的連續(xù)t-模，則(Md，*)為X上的一個模糊擬度量，稱(Md，*)是由d導(dǎo)出的標(biāo)準(zhǔn)模糊擬度量.

接下來我們介紹擬度量空間的一些基本概念.

定義5[13]設(shè)(X，d)是一個擬度量空間，若對?ε∈(0，1)，t>0，都存在n0∈N+，當(dāng)m≥n≥n0時d(xn，xm)<ε，則稱序列{xn}為左K-柯西列.

定義6[13]設(shè)(X，d)是一個擬度量空間，若(X，d)中任意的左K-柯西列是收斂的，則稱(X，d)是Smyth完備的.

則稱C為復(fù)雜性函數(shù)集，稱dC為復(fù)雜性擬度量，稱(C，dC)為復(fù)雜性(擬度量)空間.

注4容易驗證dC是C上的一個擬度量.

文獻[2]證明了復(fù)雜性空間(C，dC)是Smyth完備的.

在復(fù)雜性理論中，算法的復(fù)雜性由它的運行時間函數(shù)f(n)(n∈N+)來表示，其中f(n)被稱為算法的復(fù)雜性函數(shù).

設(shè)f，g∈C，若對?n∈N+有f(n)≤g(n)，則稱f的所有輸入效率都優(yōu)于g．顯然地，若f的所有輸入效率都優(yōu)于g，則dC(f，g)=0.

在本文中，設(shè)f，g∈C，若存在n0∈N+，使得對所有的n≥n0都有f(n)≤g(n)，我們稱f的漸近效率優(yōu)于g.

例2說明復(fù)雜性擬度量dC不適合刻畫算法的漸近效率.

2 復(fù)雜性函數(shù)集上的模糊擬度量空間

本節(jié)將在復(fù)雜性函數(shù)集C上引入模糊擬度量，以此刻畫算法的漸近效率.

定義8[9]對?f，g∈C，t>0，定義輔助函數(shù)QC

其中t∈(n，n+1]，n∈N+.

性質(zhì)1[9]對?f，g∈C，t∈(0，1]，有QC(f，g，t)=dC(f，g).

性質(zhì)2[9]對?f，g，h∈C，t，s>0，有QC(f，g，t+s)≤QC(f，h，t)+QC(h，g，s).

性質(zhì)3[9]對?f，g∈C，函數(shù)QC(f，g，·)在(0，∞)上是非增的和左連續(xù)的.

定理2設(shè)C是復(fù)雜性函數(shù)集，*是連續(xù)t-模，f，g∈C，在C×C×[0，∞)上定義函數(shù)MC，

則

證(FQM1)顯然成立.

(FQM2) 令f，g∈C，對?t>0，當(dāng)f=g時，

反之，若對?t>0，

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

則特別地當(dāng)t=1時，

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

因此

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

又由性質(zhì)1即得

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

因為dC是C上的擬度量，所以f=g.

(FQM3) 令f，g，h∈C，對?t，s≥0，不妨設(shè)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) 由性質(zhì)3可知，顯然成立.

下文中的模糊擬度量空間(C，MC，*)均為定理2中引入的模糊擬度量空間.

定理3在模糊擬度量空間(C，MC，*)中，對?f，g∈C，f的漸近效率優(yōu)于g當(dāng)且僅當(dāng)存在n0∈N+，使得對?t>n0，有MC(f，g，t)=1.

證必要性 對?f，g∈C，若f的漸近效率優(yōu)于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.

充分性 由條件，當(dāng)t∈(n0，n0+1]時，MC(f，g，t)=1，即QC(f，g，t)=0．于是，對?n≥n0，有f(n)≤g(n)，即f的漸近效率優(yōu)于g.

例3表明模糊擬度量MC可以刻畫算法的漸近效率.

例3令f(n)，g(n)為例2中的函數(shù)．經(jīng)計算得：當(dāng)n=0，1，2，…，10時f(n)>g(n)； 當(dāng)n≥11時f(n)11，QC(f，g，t)=0，即MC(f，g，t)=1．因此f的漸近效率優(yōu)于g．即模糊擬度量MC可以刻畫算法的漸近效率.

定理4模糊擬度量空間(C，MC，*)是Smyth完備的.

即

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

又由性質(zhì)1可得，對?t>0都有

即

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

3 不動點定理及其應(yīng)用

本節(jié)主要介紹模糊擬度量空間(C，MC，*)的不動點定理及其應(yīng)用.

定義9設(shè)Φ是模糊擬度量空間(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)

由性質(zhì)1可得

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

根據(jù)三角不等式得，對?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．即Φ的不動點是唯一的.

接下來我們將應(yīng)用定理5來證明與分治算法相關(guān)的遞歸方程的解的存在唯一性.

正如文獻[1，14]中所述，分治算法都是通過遞歸的方法將原始問題分解成幾個子問題來解決，每個子問題都是由相同的算法單獨解決的，然后組合后的結(jié)果就是原始問題的答案．因此，分治算法的復(fù)雜性通常由下面的遞歸方程的解來表示：

(1)

其中，n∈{bp：p∈N+}，并且h(n)<+∞．遞歸方程(1)自然地誘導(dǎo)出一個映射Φ，定義如下：

因此，Φ是一個(0，1]-壓縮的自映射．應(yīng)用定理5可得，Φ有唯一的不動點g0∈C，即為遞歸方程(1)的解.

最后我們將應(yīng)用定理5來證明與快速排序算法相關(guān)的遞歸方程解的存在唯一性.

文獻[15]在討論快速排序算法的平均案例分析時得出了一個遞歸方程T：

(2)

則h就是遞歸方程(2)的唯一解.