其主要思路是对一些高难度问题最坏情况分析往往比较悲观，而使用随机产生的输入分析算法的平均复杂度又不真正切合实际，因此对一般输入加上随机扰动并对算法进行相关的平均分析就是此方法的核心。此方法最成功的应用是成功地证明了高维线性规划上的单纯型算法的运算时间在平滑分析下是多项式的。而该算法的运算时间在最坏情况下是指数的。
首页
[{"ID":42422,"Name":"理学"},{"ID":81272,"Name":"计算机科学技术"},{"ID":81639,"Name":"计算机科学理论"},{"ID":81662,"Name":"算法学"},{"ID":81664,"Name":"算法分析"}]
. 理学 . 计算机科学技术 . 计算机科学理论 . 算法学 . 算法分析平滑分析
/smoothed analysis/
最后更新 2022-01-20
浏览 158次
相对较新的一种算法分析方法。是D.斯皮尔曼（Daniel Spielman）和滕尚华（Shang-Hua Teng）于2001年提出的。
- 英文名称
- smoothed analysis
- 提出者
- D.斯皮尔曼（Daniel Spielman）、滕尚华（Shang-Hua Teng）
- 创建时间
- 2001
- 所属学科
- 计算机科学技术
扩展阅读
- SPIELMAN D,TENG S．Smoothed analysis: an attempt to explain the behaviors of algorithms in practice．Communications of the ACM，2009，52(10)：76-84．
京公网安备 11010202008139号
