基础概念
这篇文章将为大家介绍算法与数据结构的基本概念，主要包含其定义以及各种专有词汇的解释，让大家在看后续文章或者其他相关的算法文章时知其所以然。
可以转载，但请声明源链接：文章源链接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的函数，还与所处理的数据集有关，所以我们需全面考虑它在最坏情况、最好情况、平均情况下的代价
空间复杂度
- 输入数据所占空间
- 程序本身所占空间
- 辅助变量所占空间
辅助变量所占空间是我们经常需要考虑的
注：时间复杂度与空间复杂度我们更倾向于考虑时间复杂度，现在的内存没有几十年前珍贵，但时间能带给用户更好的体验，这是其中一个原因，当然，具体情况具体分析
