算法分析与复杂性理论 实验报告 基本排序

为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以20组数据样本取平均数算得（如下表3、图11所示）： 数据规模： 耗时（ms）

100000 24 200000 51 300000 76 400000 105 500000 132 表3、合并排序在不同数据规模下排序所消耗的时间

图11、由表3数据整合而成的折线图

图形上：

形状基本符合n（线性增长） 数据上：

我们发现当数据规模增大两倍时： 当数据规模增大两倍时：

10000→20000： 24*2log22=48≈51 10000→30000：24*3log23=72≈76

2

20000→40000： 51*2log22=102≈105 其他倍数也可得到类似的结果。

结论：

我们发现，由于时间复杂度是o（nlog2n），当数据规模扩大n倍时，相应的在时间的消耗上会扩大nlog2n倍，同时我们发现，理论上乘以nlog2n后的数据普遍会略小于实际数据，这主要原因快速排序需要递归调用，递归调用需要花费额外的时间，此外轻微的误差可能是数据的差异造成或者电脑等其他因素造成。

快速排序：

图12、由图4数据整合而成的折线图

为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以20组数据样本取平均数算得（如下表4、图13所示）： 数据规模： 耗时（ms） 100000 17 200000 36 300000 56 400000 76 500000 98 表4、快速排序在不同数据规模下排序所消耗的时间

图13、由表4数据整合而成的折线图

图形上：

形状基本符合n（线性增长）

数据上：

我们发现当数据规模增大两倍时： 当数据规模增大两倍时： 10000→20000： 17*2log22=34≈36 10000→30000：17*3log23≈56 20000→40000： 26*2log22=54≈56 其他倍数也可得到类似的结果。

结论：

我们发现，由于时间复杂度是o（nlog2n），当数据规模扩大n倍时，相应的在时间的消耗上会扩大nlog2n倍，同时我们发现，理论上乘以nlog2n后的数据普遍会略小于实际数据，这主要原因快速排序需要递归调用，递归调用需要花费额外的时间，此外轻微的误差可能是数据的差异造成或者电脑等其他因素造成。

插入排序：

图14、由图5数据整合而成的折线图

为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以20组数据样本取平均数算得（如下表5、图15所示）： 数据规模： 耗时（ms）

10000 80 20000 319 30000 723 40000 1283 50000 2011 表5、插入排序在不同数据规模下排序所消耗的时间

图15、由表5数据整合而成的折线图

图形上：

2

形状基本符合n（二次增长） 数据上：

我们发现当数据规模增大两倍时： 当数据规模增大两倍时：

22

10000→20000： 80*2=320≈319 10000→30000：80*3=720≈723

2

20000→40000： 319*2=1276≈1283 其他倍数也可得到类似的结果。

结论：

2

我们发现，由于时间复杂度是o（n），当数据规模扩大n倍时，相应的在时间的消耗上会扩

2

大n倍，理论上，如果数据太具有特殊性，那此算法被影响的程度会比较大，他的的比较

22

次数可以从线性次数，到n次，赋值次数也可能由常数次变成n总的来说，受数据影响较大，由于我实验基数少，所以无法得出此结论。 。 。 。 。 。 。 。 。 。 。 。 。 。