c++ - 算法复杂度渐近线图

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，则复杂度被低估。