Manual

User Manual:

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

DownloadManual
Open PDF In BrowserView PDF
数据结构第一周实验报告
一、实现代码 1-1 和代码 1-2，并生成数据检测
令数组的大小分别为 100,1000,10000，分别测试代码 1-1 和代码 1-2，并得到运行
的时间数据，每个 size 均运行了 10 次并取平均值，python 绘图，编译环境 GCC 5.4.0

1.

使用 numpy 库拟合得到的结果分别是
y1 = 0.005438 x + 0.1111
y2 = 0.002375 x + 0.04444

从图中和拟合结果可以看出，代码 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
算法 4

2.3
0.3

3.4
0.5

10.4
1

21.6
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 下的运行时间

课本习题第一题

课本习题第二题
Source Exif Data: 
File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.7
Linearized                      : No
Page Count                      : 7
Author                          : dreamboy
Comments                        : 
Company                         : 
Create Date                     : 2018:09:14 12:16:11+04:16
Creator                         : WPS Office 社区版
Modify Date                     : 2018:09:14 12:16:11+04:16
Producer                        : 
Source Modified                 : D:20180914121611+04'16'
Subject                         : 
Title                           : 
Trapped                         : False
EXIF Metadata provided by EXIF.tools

Navigation menu