Asymptotic符号有替代方案吗？

Question

我发现了这个定义：

渐近符号是一种用于分析算法运行时间的语言，通过识别算法随着输入大小的增加而表现出的行为，来确定算法的增长速率。 这也被称为算法的增长率。

这让我想到，除了输入大小之外，是否还有其他标志或可能性来分析算法？

- Ritveak

---

相反，我很震惊这个标签竟然不存在。 - Ritveak

“无症状”意味着“没有显示出任何迹象”。这里指的是渐近复杂度。 - greybeard

最近似乎有人对“渐进符号”标签有需求。在Stackoverflow上搜索“asymptomatic”会发现近100个结果，涉及到人们讨论渐进分析、符号和边界的话题。 - kcsquared

@老灰鬍子 不，最好是cure the disease（治療疾病）而不是只解決症狀。 - kcsquared

Answer 1

是的，有很多替代方法。例如，由于渐近符号法忽略了前导系数，所以它不是用来推断确切操作计数的好工具。然而，在某些情况下，通过使用更精确的分析方法，您可以确定算法运行时间的前导系数作为输入大小的函数。这在诸如数值方法之类的领域具有应用，其中输入非常大且这些前导常数很重要。

您还可以查看算法固有的并行度，这对于想要在多核机器上运行算法非常有用。或者，您可以查看在算法并行化时需要多少通信量，这在分布式计算方面具有应用。

您还可以查看算法实现的结构元素。对于代码，您可以查看诸如圆形复杂度之类的内容，它根据该代码中存在的控制路径数量来衡量代码的“复杂性”。对于布尔电路，您可以查看电路深度。对于排序网络，您可以查看网络中的轮数。

您还可以从查看输入大小转换为查看输入的其他属性。固定参数可处理性的理念基于这样的洞察力：算法的输入可能有一个“简单”部分和一个“难”部分，如果“难”部分不是那么难，即使输入在传统意义上很大，您也可能能够快速解决问题。

您还可以分析算法对其输入的微小变化的敏感性。也许该算法在大多数实例上运行非常快，但在其他情况下极为缓慢（线性规划的单纯形法就是一个很好的例子）。像平滑复杂度之类的工具正是精确查看这些问题的。

- templatetypedef