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

Achievements and Prospects of Smoothed Analysis of Algorithms

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

There are many algorithms that work exceedingly well in practice but are known to perform poorly in the worst-case or lack good worst-case analyses. One of the most typical examples is the simplex method for linear programming. Spilman and Teng introduced the smoothed analyis of algorithms to explain the above contradiction successfully. The algorithm community pays close attention to smoothed analysis. Some concepts and the main achievements related to smoothed analysis are presented. The random perturbation model TSSP is proposed, which can overcome some limitations of the Partial Permutation model. The TSSP model is used in the smoothed analysis of algorithms like quick-sorting, whose performance is mainly determined by the initial order of the elements of an instance. A smoothed analysis of quick-sorting under the TSSP model is performed and the smoothed time complexity of quick-sorting is proved as O(2λn×log 2(n)), where λ is the random perturbation magnitude. Several prospects on smoothed analysis of algorithms are presented.