算法复杂度渐近图

Question

我正在准备一个C++项目，我必须计算出许多算法复杂度big-O，并将其与图上的理论值进行比较。我做了一个时间函数来计算算法的执行时间，但我没有找到一种方法来计算复杂度，并使用时间T和输入N绘制曲线。

有什么想法吗？

Answer 1

简而言之:如果你定义了理论复杂度T(n)，你所要做的就是对给定的n范围执行x次测试: n1，...，nx和每次测试的测量时间。然后从你的n1，...，nx集合中选择中值nm，并计算系数c，定义为:c= t(nm)/T(nm)。t( nm )是n (nm)的中位数的测量时间，T(nm)是计算nm的理论复杂度。接下来，对于n中的每一个，计算系数q，这是算法的理论和实验复杂度的一致性系数：

​

​

最后，你可以画出q(n)的图，它是渐近图，它应该渐近收敛到1。如果你的图渐近地低于1，那么理论复杂度被高估了，如果超过1，复杂度就被低估了。