python - 渐近算法以外的算法的复杂性(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 等)，你也无法像看起来那样轻松地比较算法你要!主要是你首先要明确你要衡量的是什么，这并不容易。通常，您不需要详细信息。为什么？因为我们知道我们总是可以线性加速任何算法(粗略地说，特例在这里不相关)。所以乘法常数是不相关的。

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

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