使用unix时间实用程序找到快速排序的thetha等价类

Question

我使用 time 实用程序来计算输入为 10000,20000, ...,60000 个单词的快速排序算法的用户时间，这是我得到的结果我

n( in thousands)   T(n)
1                  1.740
2                  3.7 
3                  5.83  
4                  7.93
5                  10.18  
6                  12.41

想找出的是 f(n) 使得 T(n )= theta(f(n)) 即，我需要猜测 f(n) 使得 T(n)/f(n) 接近非零常数。 我尝试了以下 f(n) 函数，但似乎没有生成常量

f(n) =n
f(n) = nlogn
f(n) = n+sqrt(n)
f(n) = n^2
f(n)=n + logn
f(n)=1/n

根据我的推断，T(n) 将 n 作为下界，将 n log n 作为上限。所以我需要一个介于这两个值之间的函数。请帮忙。

Answer 1

你有很多可能的选择。我首先将您的数据拟合到六个方程中的每一个，然后看看拟合效果如何。例如，如果您尝试绘制结果，您会立即发现它们几乎是一条直线。使用任何绘图软件都可以帮助您看到这一点。在科学和数学中，这始终是一个好主意：绘制结果！

我很懒，所以我使用 Excel 将直线拟合到您的数据，然后我找到了方程：

T(n) = 2.1379n - 0.524

带有 R² 0.9995。即使 Excel 也会为您提供这些 R² 值，以告诉您数据的拟合程度如何（您希望 R² 尽可能接近 1）。现在，这个结果非常好，你可以停在那里，但我想我会尝试将你的数据拟合到方程的其余部分，看看我得到了什么。我发现最适合您的六个函数的是：

T(n) = 0.0327n<sup>2</sup> + 1.911n + 0.219

R² 优于 0.999！现在这真是一个非常合适的选择。当然，如果您想要更高的准确性，您可能应该在 Igor（免费）而不是 Excel 中尝试此操作。尤其是已知 Excel 会给出负 R² 值。

我认为最重要的信息是，您应该始终尝试绘制结果。这些天太容易了。在那之后，我认为你太关心重新发明轮子并自己推导出这些适合的东西。有很多软件可以为您完成此操作。