algorithm - 在某些算法的时间复杂度中找到常量 c

Question

我需要帮助通过检查它们的运行时间结果来找到和逼近插入排序 (cn^2) 和归并排序 (cnlgn) 的复杂度中的常量 c。

一些背景知识，我的目的是“实现插入排序和归并排序(降序)算法并测量这两种算法的性能。对于每个算法，对于每个 n = 100、200、300、400， 500、1000、2000、4000，测量它在输入为时的运行时间

1. 已经排序，即 n, n-1, …, 3, 2,1;
2. 反向排序 1, 2, 3, … n;
3. 1、2、…、n 的随机排列。

运行时间应不包括初始化时间。"

我已经完成了两种算法的代码，并将测量值(微秒)放入电子表格中。现在，由于每个算法的每个条件的值不同，我不确定如何找到这个 c。

供引用，时间表:

          InsertionSort                    MergeSort       n      AS    RS   Random              AS     RS    Random100     12    419     231              192    191     211200     13   2559    1398             1303   1299    1263300     20    236      94              113    113     123400     25    436     293              536    641     556500     32    504     246               91     81     1051000    65   1991     995              169    246     2142000     9   8186    4003              361    370     4544000    17  31777   15797              774    751     952

如有必要，我可以提供代码。

Answer 1

几乎不可能确定这些常量的值，特别是对于使用高速缓存、管道和其他“性能事物”的现代处理器。

当然，您可以尝试找到一个近似值，然后您将需要 Excel 或任何其他电子表格。

输入您的数据，创建图表，然后添加趋势线。电子表格会为您计算常数值。