渐近算法以外的算法的复杂性（Big-O - 表示法）

Question

除了渐近复杂度（Big-O 表示法）之外，用于评估算法的最常采用的概念是什么？

示例：

假设我有以下算法调用复杂度为 O(1) 的函数 func。那么该算法的复杂度为 O(N1 x N2)。但是，如果我事先知道 N1 是有限的 [1,5]，那么最坏情况下的复杂度将是 O(5 x N2)，根据定义，它也是 O(N2).

for i in range(N1):
    for j in range(N2):
        func(i,j)

万一我可以使用函数 func2 遇到此算法的不同实现，同样复杂度为 O(1)，但现在使用不同的外循环范围 N3。该算法预计为 O(N3 x N2)。但是，如果我知道 N3 的范围是 [10,50]，那么最坏情况下的复杂度将是 O(50 x N2)，这又是 O(N2).

for i in range(N3):
    for j in range(N2):
        func2(i,j)

问题:

因此，这很容易证明渐近表示法很有用，但对于某些更具体的情况可能不是最合适的比较方法。我如何比较这两种算法？最常用的方法是什么？仅使用算法所需的迭代次数是技术上严格的指标吗？

有推荐的参考资料吗？

Answer 1

你的问题很大。了解算法复杂性和指标。

你的问题是，即使你不使用 Big-O（还有很多其他的 small-o Big-omega、small-omega、theta 等），你也无法轻松地比较算法看来你想要！主要是你首先要明确你要衡量的是什么，这并不容易。通常，您不需要详细信息。为什么？因为我们知道我们总是可以线性加速任何算法（粗略地说，特例在这里不相关）。所以乘法常数不相关。

现在，您想要的是（既不是最坏情况、最好情况也不是平均情况）更多运行ning 时间的预测函数，它与 exact复杂度。但即使在那里，也有许多陷阱和陷阱。您可能认为两个算法的精确复杂度为 3n+45，在同一平台上运行的速度会一样快，但这可能是错误的！如果您没有准确定义您的计数，那么这可能是错误的。一个可能用3n个乘法，另一个用3n个加法（或者更微妙的混合），而且运行ning的乘法和加法的时间一般是不一样的。最糟糕的是，由于架构可能使用管道、预测和其他运行时间优化，这可能会极大地改变运行宁时间。甚至环境平台也可能会引入严重的偏差，想想虚拟内存、缓存、各种编译器优化等等

所以，答案是：这取决于你想预测什么......这就是为什么有这么多复杂性措施。

渐近算法以外的算法的复杂性（Big-O - 表示法）

Complexity of algorithms other than asymptotic (Big-O - notation)

python

algorithm

performance

complexity-theory