文章目录
1. 绪论
1.1 概述
1.2 数据与数据结构
1.2.1 术语
1.2.2 逻辑结构
1.2.3 存储结构:
1.2.4 数据操作:
1.3 算法
1.3.1 算法特性
1.3.2 算法目标
1.3.3 算法分析:概述
1.3.4 算法分析:时间复杂度(大O)
1.3.5 算法分析:最好、最坏、平均
1.4 回顾:西格玛Σ 求和
1. 绪论
1.1 概述
-
算法 + 数据结构 = 程序
-
程序:计算机指令的组合
-
算法:程序的逻辑抽象
-
数据结构:数据及其关系的反映,从逻辑结构和存储(物理)结构。
-
-
数据结构解决具体问题:
-
数据的逻辑结构(数学模型)
-
数据的存储结构
-
数据操作与运算
-
1.2 数据与数据结构
1.2.1 术语
-
数据(Data):数据是信息的载体,是对客观事物的符号表示。
-
数据元素(Data Element):是数据的基本单位,是一个个体。相当于表的一行。
-
数据项(Data Item):是数据元素的组成部分。相当于表的列。
-
数据对象(Data Object):性质相同的数据元素的集合。相当于表。
-
数据结构(Data Structure):特定关系的数据元素的集合。
1.2.2 逻辑结构
-
逻辑结构:数据元素之间的逻辑关系,与数据存储无关,独立与计算机之外。
-
数据元素按照特性:
-
集合:元素之间没有关系,比较松散
-
线性结构:元素之间存在==一对一==关系。除了开始和终端结点,其他结点由有一个前驱和一个后继。
-
树形结构:元素之间存在==一对多==关系。
-
图形结构:元素之间存在==多对多==关系。
-
-
数据的逻辑结构需要2部分:数据元素(data)、数据元素的关系(relationship)
1.2.3 存储结构:
-
存储结构:数据的存储结构,也称为物理结构,是数据的逻辑结构在计算机的实现。
-
数据元素的值存储表示和逻辑关系。
-
-
存储结构的4种方式:
-
顺序存储:在一片连续的存储空间中进行存储,元素的逻辑位置和物理位置保持一致。例如:数组
-
链式存储:可以存储在任意的物理物质上,需要额外的部分存放逻辑关系的指针。例如:链表
-
索引存储:存储数据的同时,额外的存储一个索引表。在查询时可以提高效率。
-
散列存储:一般情况物理上可以是连续的存储空间,需要通过
散列函数hash
来确定存储位置。在查询时可以提高效率。
-
1.2.4 数据操作:
-
初始化:创建、销毁:
-
数据操作:插入/添加、删除、修改
-
数据使用:查找、遍历
1.3 算法
-
算法:对特定问题求解步骤的一种描述。是指令的有限序列。
1.3.1 算法特性
-
有穷性:有限
-
确定性:需求确定、指令确定
-
有效性:指令都是由意义
-
输入:
-
输出:
1.3.2 算法目标
-
正确性:基本要求,需求和实现对应。
-
可读性:使程序员能够读懂,编写代码时可以辅助注释。
-
健壮性:临界值的处理、无效数据的校验等。
-
高效性:使用较少的资源(资源分2种:时间资源、空间资源)。一个好的算法要做到执行时所需时间尽量短,所需的最大存储空间尽量少。
1.3.3 算法分析:概述
-
算法的复杂度是衡量算法优劣的重要依据。
-
算法的复杂度分类:时间复杂度、空间复杂度。
-
时间复杂度:执行时间的长短。
-
空间复杂度:执行时空间需求量,也就是计算机资源的使用量。
-
1.3.4 算法分析:时间复杂度(大O)
-
主要考虑因素:
-
算法本身
-
问题规模
-
程序语言选择
-
编译程序(JDK优劣)
-
硬件速度
-
运行软件
-
-
时间复杂度通过
大O表示法
进行表示的-
大O表示法,用于估算一个算法的执行时间。
-
算法执行时间:Σ(指令的执行次数 * 指令的执行时间)。
-
指令的执行时间
是固定的,可以不考虑。只需要考虑指令的执行次数
即可。 -
大O表达法,通过统计
指令的执行次数
,就可以估算出一个算法的优劣。 -
指令的执行次数
:每行代码执行的次数,将所有的次数累加
在一起即可。 -
例如1.7:2n^3 + 3n^2+2n+1 总次数表达式 --> 只考虑最高次幂 --> O(n^3)
-
大O表达式只需要考虑最高次幂的项。
-
-
大O表达式常见的形式
-
常量阶:O(1) ,执行的次数与输入无关。
-
线性阶:O(n) ,执行的次数与输入成正比关系。例如:一层循环。
-
平方阶:O(n^2) , 执行的次数与输入成平方关系。例如:二层循环
-
立方阶:O(n^3) ,执行的次数与输入成立方关系。例如:三层循环
-
对数阶:O(log2n) , 执行的次数与输入成开方关系。例如:求对数 log28 = 3
-
线性对数阶:O(nlog2n)
-
-
O(log2n) 指数计算:R表示次数
-
O (n) :一层循环
-
O(n^2):二层循环(99乘法表)
int n = 9; for(int i = 0 ; i < n ; i ++) {for(int j = 0 ; j < n : j ++) {// 次数 n*n} }
-
O(n^3):三层循环
int n = 9; for(int i = 0 ; i < n ; i ++) { //时针for(int j = 0 ; j < n : j ++) { //分针for(int m = 0 ; m < n ; m++) { //秒针// 次数 n * n * n}} }
1.3.5 算法分析:最好、最坏、平均
-
实例:从数组中获得内容 a[1...n]
-
最好时间复杂度:获得最好的情况,例如:数组中的第一个数据。O(1)表示此情况。
-
最坏时间复杂度:获得最坏的情况,例如:数据中最后一位。O(n)表示此情况。
-
平均时间复杂度:
-
1+...+n和 : (n+1) * n/2
-
平均,和/n :(n+1) * n/2 / n ---> (n + 1) / 2 --> O(n)表示
-
-
结论:在一般情况下,取
最坏时间复杂度
或等概率下的平均时间复杂度
作为算法的时间复杂度。
1.4 回顾:西格玛Σ 求和
-
需求:1+2+3+4+....+n
$$
\sum_{i=1}^{n}\dfrac{(n+1)*n}{2} \tag{西格玛Σ求和}
$$