算法复杂度与 运行 时间
Algorithm Complexity vs Running Time
我有一个用于信号量化的算法。对于该算法，我有一个等式来计算其具有不同参数值的复杂性。该算法是用 C 实现的。有时根据等式我的复杂度较低，但 运行 时间较高。我不是 100% 确定方程式。
我的问题是运行时间和算法复杂度总是有直接关系？意思是，总是我们拥有的复杂性越高，运行 时间就会越长？还是一种算法与另一种算法不同？
时间复杂度更多地是衡量时间如何随输入大小变化的指标，而不是绝对指标。
（这是一种极端的简化，但它可以解释您所看到的现象。）
如果 n 是你的问题规模，而你的实际 运行 时间是 1000000000 * n，它具有线性复杂度，而 0.000000001*n^2 将是二次的。
如果将它们相互比较，您会发现 0.000000001*n^2 一直小于 1000000000 * n，直到 n = 1e18 左右，尽管 "greater complexity"。
（0.000000001*n^2 + 1000000000 * n 也是二次方的，但执行时间总是比两者都差。）
不，运行宁时间和算法复杂度没有简单的关系。
估计或比较 运行 次很容易变得非常复杂和详细。即使使用相同的程序和输入数据，也有许多变量会发生变化 - 这就是基准测试执行多个 运行 并对其进行统计处理的原因。
如果您正在寻找较大的差异，通常最重要的两个因素是算法复杂性 ("big O()") 和启动时间。通常，较低的 "big O()" 算法需要更复杂的启动；也就是说，在进入实际循环之前需要在程序中进行更多初始设置。如果初始设置比 运行 小数据集算法的其余部分花费的时间更长，则较大的 O() 额定算法将 运行 更快 对于那些小数据集。对于大数据集，较低的O()算法会更快。总时间相等的数据集大小，称为"crossover"大小。
对于性能，作为选择要实施的算法的一部分，您需要检查您的大部分数据是否高于或低于该交叉点。
在运行时间预测中获得越来越多的细节和准确性会变得非常复杂。
我有一个用于信号量化的算法。对于该算法，我有一个等式来计算其具有不同参数值的复杂性。该算法是用 C 实现的。有时根据等式我的复杂度较低，但 运行 时间较高。我不是 100% 确定方程式。
我的问题是运行时间和算法复杂度总是有直接关系？意思是，总是我们拥有的复杂性越高，运行 时间就会越长？还是一种算法与另一种算法不同？
时间复杂度更多地是衡量时间如何随输入大小变化的指标，而不是绝对指标。
（这是一种极端的简化，但它可以解释您所看到的现象。）
如果 n 是你的问题规模，而你的实际 运行 时间是 1000000000 * n，它具有线性复杂度，而 0.000000001*n^2 将是二次的。
如果将它们相互比较，您会发现 0.000000001*n^2 一直小于 1000000000 * n，直到 n = 1e18 左右，尽管 "greater complexity"。
（0.000000001*n^2 + 1000000000 * n 也是二次方的，但执行时间总是比两者都差。）
不，运行宁时间和算法复杂度没有简单的关系。
估计或比较 运行 次很容易变得非常复杂和详细。即使使用相同的程序和输入数据，也有许多变量会发生变化 - 这就是基准测试执行多个 运行 并对其进行统计处理的原因。
如果您正在寻找较大的差异，通常最重要的两个因素是算法复杂性 ("big O()") 和启动时间。通常，较低的 "big O()" 算法需要更复杂的启动；也就是说，在进入实际循环之前需要在程序中进行更多初始设置。如果初始设置比 运行 小数据集算法的其余部分花费的时间更长，则较大的 O() 额定算法将 运行 更快 对于那些小数据集。对于大数据集，较低的O()算法会更快。总时间相等的数据集大小，称为"crossover"大小。
对于性能，作为选择要实施的算法的一部分，您需要检查您的大部分数据是否高于或低于该交叉点。
在运行时间预测中获得越来越多的细节和准确性会变得非常复杂。