0

我编写了合并和堆排序并计算了运行时复杂度，我想现在从我收集的数据中找到用于合并和堆排序的常数 c (c*(n*lg(n)))。以下是元素数（n）与运行时间（秒）的两个图表公式（来自excel），我将如何计算c常数？任何帮助将不胜感激！谢谢你。

堆：y = 5E-12x2 + 2E-05x - 0.0561

合并：y = 9E-10x2 - 9E-05x + 2.0958

4

1 回答 1

0

您给出的公式是 f( n ) = an 2 + bn + c形式的多项式，具有常数a、b和c。这些不会帮助你。

您需要将 f( n ) = an lg( n ) + bn + c形式的方程拟合到您的数据中。不是多项式，而是一个包含n lg( n ) 项的方程。该术语的系数是您被要求的。线性 ( b ) 和常数 ( c ) 项无关紧要。只是n lg( n ) 项上的常数，因为它增长最快。

于 2012-10-17T02:08:05.343 回答