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

• 作者: 朱洪 杨智应 雷向欣
• 来源期刊: 计算机研究与发展
• 学科: 工学
• 关键词: 平滑分析 平滑复杂性 TSSP模型 k-邻域
• 年，卷（期）: 2005,（2）
• 所属期刊栏目: 算法理论
• 页码范围: 286-293
• 页数: 8页
• 分类号: TP301.6
• 字数: 7570字
• 语种: 中文

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨智应	上海海事大学计算机科学与技术系	29	82	5.0	8.0
2	雷向欣	复旦大学计算机与信息技术系	2	14	2.0	2.0
3	朱洪	复旦大学计算机科学与工程系	29	159	7.0	12.0