基础概念
这篇文章将为大家介绍算法与数据结构的基本概念,主要包含其定义以及各种专有词汇的解释,让大家在看后续文章或者其他相关的算法文章时知其所以然。
可以转载,但请声明源链接:文章源链接justin3go.com(有些latex公式某些平台不能渲染可查看这个网站)
数据结构
基础概念
- 数据:信息的载体,能够被计算机识别、存储、加工、处理。
- 数据元素:数据的基本单位,数据元素可由若干个数据项构成。
- 数据对象:数据的子集,具有相同性质的数据元素的集合。
- 数据结构:由数据元素和结构(元素之间的相互关系)组成。
Data_Stryctrues=(D,S)Data_Stryctrues=(D,S)
- 逻辑结构:集合、线性结构、树形结构(非线性)、图形结构(非线性)。
- 关系:<a_i, a_j> 或 (a_i, a_j) ------前驱或弧尾<=>后续或弧头
数据的物理结构
逻辑结构在存储器中的映象
- 数据元素的存储(图就是存每个顶点的信息)
- 关系的存储(图就是存各个顶点的关系,比如邻接矩阵的方式存储)
关系的描述方式
- 顺序存储结构
- 链式存储结构
算法
基础概念
- 算法:对特定问题求解步骤的一种描述,是指令的有限序列(有顺序)。
- 特性:有穷性、确定性、可行性、输入、输出。
注:输入可以为空,但没有输出的算法是毫无意义的。
- 程序与算法:
- 程序不一定满足有穷性(比如操作系统)。
- 程序的指令必须是计算机可执行的,算法的指令无此限制。
- 如果用机器可执行的语言书写算法,那么算法就是程序。
- 算法设计的原则
- 正确性:应当满足具体问题的要求。
- 健壮性:处理异常。
- 可读性
- 执行算法所消耗的时间(量化)
- 执行算法所消耗的存储空间(量化)
时间复杂度
简要
算法所消耗的时间:算法中所有语句执行时间(语句的频度--语句重复执行的次数)之和
for i in range(n): #n+1 for j in range(n): #n*(n+1) C[i][j] = 0 #n*n for k in range(n): #n*n*(n+1) C[i][j] = C[i][j] + B[i][j] #n*n*n
T(n):2n3+3n2+2n+1T(n):2n3+3n2+2n+1
渐进时间复杂度
O(n3)O(n3)
注:都是求最坏情况下的原操作句执行次数,平均情况也是一种不错的衡量假设
常见算法时间复杂度
O(c)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(2n)<O(n!)<O(n3)<O(nn)O(c)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(2n)<O(n!)<O(n3)<O(nn)
算法的时间复杂度不仅是问题规模n的函数,还与所处理的数据集有关,所以我们需全面考虑它在最坏情况、最好情况、平均情况下的代价
空间复杂度
- 输入数据所占空间
- 程序本身所占空间
- 辅助变量所占空间
辅助变量所占空间是我们经常需要考虑的
注:时间复杂度与空间复杂度我们更倾向于考虑时间复杂度,现在的内存没有几十年前珍贵,但时间能带给用户更好的体验,这是其中一个原因,当然,具体情况具体分析