在学术界外是否使用平滑分析？

Question

做了 平滑分析 找到算法主流分析的方式？算法设计人员将平滑的分析应用于其算法是否常见？

Answer 1

我可能错了，但我认为平滑的分析是一种 解释 具有不良理论保证的算法的实践内行为（单纯词，K-均等等）。我不确定这意味着什么 利用 在实践中进行平滑分析，除了证明使用特定的启发式态度具有不良案例表现的合理性（“我的启发式术语具有blah等等最差的行为，但平滑的分析表明，它在实践中会很好地表现出色等”）

Answer 2

人们分析现实世界中的算法的方式与学术界大不相同。在学术界，目标是在运行时间找到一个可证明的上限，但在现实生活中，目标是了解算法的工作原理，哪些调整可以改善运行时间。学术界有两种主要方法，但在实践中使用：

• 近似方法。在这里，您使用许多简化的假设来预测算法的运行时间。类似于理论物理学家（过去）。
• 实验。您运行算法并测量几个统计信息 - 每个部分花了多少时间，每个功能的次数，每个分支多久运行一次，依此类推。该信息可用于优化算法。还使用实验来找出在分析实践中分析算法工作时是否完成了一些近似值。

也就是说，除了在相关的学术出版物中添加一些填充文本之外，我认为分析算法并不常见。重点是软件工程或低级优化，具体取决于主题。

最后，平滑的分析是一种启发式，可以用来解释为什么算法在实践中比最坏情况所暗示的更好的作用 - 即，由于某些意义上的某些输入是“随机”的。如果使用近似方法，则可以使用这种启发式算法来近似算法的行为。