渐近表示法有其他选择吗？
我找到了这个定义：
渐近符号是一种通过识别算法随着算法输入大小增加的行为来分析算法运行时间的语言。这也称为算法的增长率。
这让我思考，是否还有其他符号，或者是否有可能使用除输入大小之外的任何度量来分析算法？
I found this definition :
Asymptotic Notations are languages to analyze an algorithm's running time by identifying its behavior as the input size for the algorithm increases. This is also known as an algorithm's growth rate.
This got me thinking, are there any other notations, or is there even a possibility of having any metric, other than input size, to analyze an algorithm?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
是的，有很多选择。例如，由于渐近表示法忽略了前导系数，因此它不是推理精确运算计数的好工具。然而，在某些情况下，使用更精确的分析，您可以确定算法运行时间的主导系数是输入大小的函数。这在数值方法等领域有应用，这些领域的输入量很大并且这些主要常数很重要。
您还可以查看算法固有的并行度，如果您想在多核计算机上运行该算法，这将很有用。或者你可能会看看算法并行化时需要多少通信，这在分布式计算中有应用。
您还可以查看算法如何实现的结构元素。对于代码，您可以查看诸如圈复杂度之类的东西，它根据一段代码存在的控制路径的数量来衡量一段代码的“复杂”程度。对于布尔电路，您可以查看电路的深度。对于排序网络，您可以查看网络中的轮数。
您还可以从查看输入的大小切换到查看输入的某些其他属性。固定参数易处理性的想法基于这样的见解：算法的输入可能有“简单”部分和“困难”部分，如果“困难”部分不是那么难，您可能能够解决即使传统意义上的输入很大，问题也会很快解决。
您还可以分析算法对其输入的微小变化的敏感性。也许该算法在大多数情况下运行得非常快，但在其他情况下却非常慢（线性规划的单纯形方法就是一个很好的例子）。像平滑复杂性这样的工具正是针对这一点的。
Yes, there are many alternatives. For example, since asymptotic notation ignores leading coefficients, it’s not a great tool for reasoning about exact operation counts. However, using more precise analyses, in some cases you can pin down what the leading coefficient of an algorithm’s runtime is as a function of input size. This has applications in areas like numerical methods where inputs are huge and these leading constants matter.
You might also look at the degree of parallelism inherent in an algorithm, which would be useful if you wanted to run the algorithm on a multicore machine. Or you might look at how much communication is required when the algorithm is parallelized, which has applications in distributed computing.
You might also look at structural elements of how an algorithm is implemented. For code, you can look at things like the cyclomatic complexity, which measures how “complex” a piece of code is based on how many control paths exist through it. For Boolean circuits, you could look at the depth of the circuit. For sorting networks, you could look at the number of rounds in the network.
You could also switch from looking at the size of the input to some other property of the input. The idea of fixed-parameter tractability is based on the insight that an input to an algorithm might have an “easy” part and a “hard” part, and if the “hard” part isn’t that hard you might be able to solve the problem quickly even if the input is large in a conventional sense.
You could also analyze the algorithm’s sensitivity to tiny changes to its input. Perhaps the algorithm runs extremely quickly on most instances, but is painfully slow in others (the simplex method for linear programming is a good example of this). Tools like smoothed complexity look at precisely this.