算法复杂性平滑分析的研究进展与展望

有很多算法其最坏情况复杂性很坏 (甚至是指数阶的 ) ,但在实际应用中却很有效 其中一个典型代表就是求解线性规划问题的单纯形算法 最近 ,Spielman和Teng提出了算法的平滑复杂性概念及算法复杂性平滑分析方法 ,对上述矛盾给出了合理的解释 ,在理论计算机科学界引起了极大的关注 为此 ,做了以下工作 :介绍算法复杂性平滑分析的基本概念 ;介绍两年多来算法复杂性平滑分析主要的研究进展 ;从实际应用出发提出一个更合乎算法复杂性平滑分析思想的随机扰动模型 (简称TSSP模型 ) ,克服“PartialPermutation”随机扰动模型的不足 ,并证明在TSSP模型下快速排序算法的时间平滑复杂性为O(2λn×log2 (n) ) ,其中λ是随机扰动幅度大小 最后 。