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

Application of Fuzzy Quasi-Metric in Complexity Analysis

在复杂性理论中,复杂性分析主要是针对算法的效率进行分析.通常地,在复杂性分析中更多的是研究算法的渐近效率.近年来,拟度量在复杂性分析中的应用受到学者们的广泛研究,但是它也存在着一定的局限性,例如拟度量并不适合刻画算法渐近效率的高低.为了解决这个问题,本文引入了复杂性函数集上的模糊拟度量,并以此刻画了算法渐近效率的高低.同时,通过研究它的基本性质,建立了一个不动点定理,并应用该不动点定理研究了与分治算法相关的递归方程的解的存在性和唯一性,以及与快速排序算法相关的递归方程的解的存在性和唯一性.以上结果构建起了模糊拟度量和算法的渐近效率之间的联系,为模糊拟度量在算法应用方面的进一步研究提供了一种新的有效途径.

In complexity theory,complexity analysis is mainly aimed at the efficiency of the algorithm.Generally,in complexity analysis,more attention is paid to the asymptotic efficiency of the algorithm.In recent years,the application of quasi-metric in complexity analysis has been widely studied by scholars,but it also has some limitations.For example,quasi-metric is not suitable for describing the asymptotic efficiency of algorithms.In order to solve this problem,a fuzzy quasi-metric in a complexity space is introduced and used to describe the asymptotic efficiency of algorithms.After giving some results of the fuzzy quasi-metric,a fixed point theorem in a complexity space is established.As its application,the existence and uniqueness of the solution of recurrence equations associated with Divide-and-Conquer algorithm and the existence and uniqueness of the solution of recurrence equations associated with Quicksort algorithm are proven.The above results construct the relationship between fuzzy quasi-metric and the asymptotic efficiency of the algorithm,and provide a new and effective approach for the further research of application of fuzzy quasi-metric in algorithms.