Manual

User Manual:

Open the PDF directly: View PDF .
Page Count: 7

数据结构第一周实验报告

一、实现代码 1-1 和代码 1-2，并生成数据检测

令数组的大小分别为 100,1000,10000，分别测试代码 1-1 和代码 1-2，并得到运行

的时间数据，每个 size 均运行了 10 次并取平均值，python 绘图，编译环境 GCC 5.4.0

使用 numpy 库拟合得到的结果分别是

y1 = 0.005438 x + 0.1111

y2 = 0.002375 x + 0.04444

1. 从图中和拟合结果可以看出，代码 1-1 拟合曲线的斜率大致为代码 1-2 拟合曲线

的2倍，并且与数组的大小呈线性关系，这符合时间复杂度的分析

代码 1-1，时间复杂度 O(2N) = O(N)

代码 1-2，时间复杂度 O(N)

2. 从图中可以看出，当数组的 size 越小，两个算法耗费的时间越接近，随着 size 的

增加，算法二的优势越明显

二、求最大子序列的四种算法

考虑到 size 过大时运行时间过长，这里取 size 为50,100,200,400,分别测试四种算

法，并得到运行的时间。由于算法一运行的时间远高于其它三种算法，故为了便于观察将算

法一的图像单独列出。这里以表格形式给出了运行时间，折线图以及拟合图像

运行时间(us)/数

组大小

50

100

200

400

算法 1

54.2

434.7

3431

27428

算法 2

5.2

15.2

89.2

241.4

算法 3

2.3

3.4

10.4

21.6

算法 4

0.3

0.5

1

3.2

y1 = 0.0004334 x^3 - 0.003212 x^2 + 0.5612 x - 20

Y2 = 0.0006394 x^2+ 0.4047 x - 22.1

Y4 = 0.008452 x - 0.3348

（由于样本点较少且运行时间相差较大，故拟合效果不是很好，但足以反映相

对彼此的运行快慢）

三、完成书上习题

见源代码

求素数的算法在最坏的情况下，时间复杂度为 O(√n)

附图：

1-1 与1-2 的比较

4种算法在 4个不同 size 下的运行时间

课本习题第一题

课本习题第二题