有渐近符号的替代方案吗



我发现了这个定义:

渐近符号是通过识别算法输入大小增加时的行为来分析算法运行时间的语言。这也被称为算法的增长率。

这让我思考,除了输入大小之外,还有其他符号吗,或者有没有可能使用任何度量来分析算法?

是的,有很多替代方案。例如,由于渐近表示法忽略了前导系数,所以它不是推理精确运算计数的好工具。然而,使用更精确的分析,在某些情况下,你可以确定算法运行时的主导系数是多少,作为输入大小的函数。这在数值方法等领域有应用,在这些领域,输入量巨大,而这些主要常数很重要。

您还可以查看算法中固有的并行度,如果您想在多核计算机上运行该算法,这将非常有用。或者,您可以看看当算法并行化时需要多少通信,这在分布式计算中有应用。

您还可以查看如何实现算法的结构元素。对于代码,你可以看看圈复杂度,它根据代码中存在的控制路径数来衡量代码的"复杂度"。对于布尔电路,你可以看电路的深度。对于排序网络,您可以查看网络中的轮次数量。

您还可以从查看输入的大小切换到查看输入的其他属性。固定参数易处理性的想法是基于这样一种观点,即算法的输入可能有"容易"部分和"难"部分,如果"难"的部分没有那么难,即使在传统意义上输入很大,你也可能快速解决问题。

您还可以分析算法对输入微小变化的敏感性。也许该算法在大多数情况下运行得非常快,但在其他情况下却非常慢(线性规划的单纯形法就是一个很好的例子(。像平滑复杂性这样的工具正是着眼于此。

最新更新