如何通过运行时来计算算法的复杂度？

Question

我正在测试排序算法，并尝试了不同数据量的排序算法。10万元素，100万元素，1000万元素。

我需要通过每次排序所花费的时间来计算这个算法的复杂性。

我怎么能这么做？

Answer 1

如果不进行数学分析，你就无法找到算法的运行时间，而经验测量可以让你合理地了解算法的运行时间--或者更确切地说是程序--是如何运行的。

例如，如果您有n度量值(x1, y1), (x2, y2), ..., (xn, yn)，其中xi是输入的大小，而yi是这个大小的输入的程序时间，那么您可以绘制函数以查看它是否是一个多项式。在实践中，情况往往如此。然而，很难从图中看出指数应该是多少。

要找到指数，可以找到最适合点(log xi, log yi)的直线的斜率。这是因为如果是y=C*x^k+lower order terms，那么既然C*x^k这个词占主导地位，那么当“原始”方程是多项式方程的时候，它就会是线性的。(每当在测井图中看到线性函数时，运行时间都是多项式；直线的斜率告诉您多项式的程度。)

下面是二次函数y(x)=x^2的一幅图：

​

下面是相应的日志图：

​

我们可以看到，这是一条与斜率2的线(实际上，您可以使用线性最小二乘来计算这个值。这是预期的，因为log y(x) = 2 * log(x)。

我使用的代码：

x = 1:1:100;
y = x.^2;
plot(x, y);
plot(log(x), log(y));

在实践中，该函数看起来比较混乱，只有在没有其他功能可用时，斜率才能(或应该)作为经验法则使用。

我想还有许多其他技巧可以从运行时间度量中了解程序行为。我会给别人一个机会分享他们的经验。