文档介绍：数据结构与算法分析 – C++语言描述(第二版)
第1章软件开发(p1-p39 自学为主) 如何进行软件开发 第2章抽象数据类型入门(p40-p72 自学为主) ADT概念、C++的数据类型 第3章数据结构和抽象数据类型(p73-p128 自学为主) 数据结构概念、数组 第10章 算法效率
Start to Solve them!
学****准备1:数据结构初步
数据结构课程讨论的中心问题:
复杂的实际问题需要处理大量的数据,数据之间又有错综复杂的关系,在机器中如何有效的表示(存储)这些数据和数据之间的联系,使它们可以在相关的处理程序中有效的用来模拟和解决问题。
图:数据结构的地位及其相关领域的联系
数据结构
设计方法
描述语言
算法理论
数据模型
问题求解
本课程的讨论重点
一些典型的数据结构:
字符串
列表(基于数组/基于链)
栈/队列
树/二叉树
堆/优先队列
散列
图
一些典型的算法:
添加
删除
查找/搜索
排序
最短路径
可达/连通
对数据结构的关注点:
结构中各元素之间的抽象(逻辑)关系—逻辑结构
结构中各元素的存储方式—存储结构
结构的行为和特性—数据的添加、删除、查找、排序等。
逻辑结构-ADT(本书中对应的内容描述)
线性
非线性
存储结构-”数据结构”
连续存储:数组
链式存储:使用指针
结构的行为和特性-算法
各类算法描述和实现
算法效率的分析
逻辑结构
线性结构
…
一个头,一个尾巴
头无前驱,尾无后继
其他元素有唯一的前驱与后继.
如:字符串、链表、堆栈/队列
逻辑结构
非线性结构
元素的前驱后继个数不确定、
如:树/二叉树、散列、图
算法:为实现某个计算过程而规定的基本动作的执行序列(可以被计算机执行的一个过程)
Niklaus Wirth,Pascal语言的创始人
算法+数据结构=程序
算法特性:
-无二义性。算法的每个步骤必须准确描述,让计算机知道每个指令要求完成什么。
-简单性。计算机可以实现,通常采用类似程序的形式描述,容易实现为计算机指令。
-可终止性。算法必须在有限步(合理的时间内)终止。
-正确性。满足初始条件的输入,无论算法执行几次,算法得到的结果总是确定并且正确的。
-(补充)>=0个输入,>=1个输出。可以有0个或多个输
入,有至少1个输出。
算法分析(第10章 p489): 评价一个算法优劣。
时间和空间。
空间复杂度:当被解决问题的规模(以某种单位计)从1n时,解决问题的算法所需占用的空间也以某种单位从f(1)f(n),此时称算法的空间代价是f(n)。
时间复杂度:当被解决问题的规模(以某种单位计)从1n时,解决问题的算法所需耗费的时间也以某种单位从g(1)g(n),此时称算法的时间代价是g(n)。
算法复杂度(效率)的表示: 大O表示法
Big-O 定义:
若存在常量c,n0,对于任意的n≥n0,有T(n) ≤c·f(n).
则认为 T(n)=O(f(n)).称O(f(n))为算法复杂度
---当n充分大时,算法的复杂度不大于 f(n)的常数倍
Big-O 的加法规则:
T(n)=T1(n)+T2(n)=O(f1(n))+O(f2(n))=O(max(f1(n)+f2(n)))
Big-O 的乘法规则:
T(n)=T1(n)XT2(n)=O(f1(n))XO(f2(n))=O((f1(n)Xf2(n)))
Big-O 举例:
1) f(n)=(1/2) n2 <=n2 ,n>=1 f(n)=O(g(n))=O( n2 )
2) f(n)=n+2<=n+n=2*n,n>=2 f(n)=O(n)
3) f(n)= n2 + n + 16, f(n)=O( n2 )
4) f(n)= n2 + n + 1<= n2 + n2 + n2 = 3 n2 ,n>=1 f(n)=O( n2 )
5) f(n)= <= ,n>=3 f(n)=O( )
6) f(n)= 2n + n+2 <= 2n + 2n + 2n =3 * 2n ,n>=1
f(n)=O( 2n )
√n+3
√2n
√n