algorithm - 时间复杂度和实验结果

Question

我有两种算法 A 和 B，它们适用于逻辑图，我想比较它们在时间上的效率。

当我计算两种算法的时间复杂度时，我发现：

Time Complexity of A: O(2*n*n)
Time Complexity of B: O((n*n)/2)

根据维基百科，http ://en.wikipedia.org/wiki/Time_complexity 我们在计算时间复杂度时忽略了系数，这会产生：

Time Complexity of A: O(n^2)
Time Complexity of B: O(n^2)

我做的第二步是通过实验计算每种算法对不同大小的图所花费的时间。下面，x 轴代表图中的节点数，y 轴是时间，以秒为单位。

正如您所看到的，对于大图，两种算法之间存在很大差异。我的问题是：这合理吗？是否有可能有两种算法具有相同的时间复杂度，但在实践中却存在如此大的时间差异？谢谢你。

Answer 1

是的，这绝对合理。计算复杂度并没有显示算法到底有多快——而是显示了它如何对输入大小的变化做出反应。

这不是巧合渐近复杂性被称为渐近而不是“相同”。