c - 算法复杂度与运行时间

Question

我有一个用于信号量化的算法。对于算法，我有一个方程来计算不同参数值的复杂性。该算法是用 C 实现的。有时根据等式，我的复杂性较低，但运行时间较高。我不是 100% 确定方程。

我的问题是运行时间和算法复杂度一直有直接关系吗？意味着，我们的复杂性越高，运行时间就越长？还是从一种算法到另一种算法不同？

Answer 1

时间复杂度更多地是衡量时间如何随输入大小而变化的衡量标准，而不是绝对衡量标准。
（这是一个极端的简化，但它可以解释你所看到的现象。）

如果n是您的问题大小并且您的实际运行时间是1000000000 * n，则它具有线性复杂性，而0.000000001*n^2将是二次的。

如果您将它们相互绘制，您会发现它0.000000001*n^2小于1000000000 * nn = 1e18 左右，尽管它“更复杂”。

（0.000000001*n^2 + 1000000000 * n也将是二次的，但执行时间总是比两者都差。）

Answer 2

不，运行时间和算法复杂度没有简单的关系。

估计或比较运行时间很容易变得非常复杂和详细。即使使用相同的程序和输入数据，也有许多变量会发生变化——这就是为什么基准测试会进行多次运行并以统计方式处理它们的原因。

如果您正在寻找较大的差异，通常两个最重要的因素是算法复杂性（“大O ()”）和启动时间。通常，较低的“big O ()”算法需要更复杂的启动；也就是说，在进入实际循环之前，它需要在程序中进行更多的初始设置。如果对小数据集执行该初始设置比运行算法的其余部分花费更长的时间，那么对于那些小数据集，较大的O () 评级算法将运行得更快。对于大数据集，较低的O () 算法会更快。将有一个总时间相等的数据集大小，称为“交叉”大小。

为了提高性能，您需要检查大部分数据是否高于或低于该交叉点，作为选择要实施的算法的一部分。

在运行时预测中获得越来越多的细节和准确性会很快变得更加复杂。