datetime:2022-04-09 17:46
author:nzb
数据结构与算法
绪论
基本概念
数据
数据元素、数据项
数据对象、数据结构
数据类型、抽象数据类型（ADT）
数据结构三要素
逻辑结构
集合
线性结构
树形结构
图状结构（网状结构）
物理结构（存储结构）
顺序存储
物理内存中是连续的非顺序存储
物理内存中是分散的链式存储
索引存储
散列存储
数据的运算
学习建议
- 概念多，比较无聊。抓大放小，重要的是形成框架，不必纠结细节概念。
算法
程序 = 数据结构 + 算法
数据结构是要处理的信息
算法是处理信息的步骤
算法的五个特性
有穷性
有穷时间内能执行完算法是有穷的
程序可以是无穷的
确定性
相同的输入只会产生相同的输出可行性
可以用已有的基本操作实现算法输入
丢给算法处理的数据输出
算法处理的结果
“好”算法的特质
正确性
能正确解决问题可读性
对算法的描述能让其他人也看得懂健壮性
算法能处理一些异常状况高效率与低储存量需求
即算法执行省时、省内存
时间复杂度、空间复杂度
时间复杂度和空间复杂度
时间和空间增长的趋势时间复杂度
时间开销与问题规模 n 之间的关系如何计算
找到一个基本操作（最深层循环）
分析该基本操作的执行次数 x 与问题规模 n 的关系 x = f(n)
x 的数量级 O (x) 就是算法时间复杂度 T(n)
大 O 表示法（Big O）：，T (n) = O ( f(n) )
T(n)：算法的渐进时间复杂度 f(n)：代码执行次数 O：正比例关系
常用技巧
加法法则：O (f(n)) + O(g(n)) = O (max(f(n),g(n)))
乘法法则：O(f(n)) x O(g(n)) = O(f(n) x g(n))
记忆技巧：常对幂指阶
常见的时间复杂度量级
x 轴：输入问题的量级；y 轴：时间的复杂度
O (1)
O (logN)
- 设想需要 K 次循环 i 就会大于等于 n；则2^k = n；k = log2n
O (n)
解释
int i =1：执行一次
i<=n；i++；x++：各执行3次
所以复杂度：O (1 + 3N) = O (N)；因为 Big O 计算的是 N 接近于无限大的情况下，所以常量 1 和 倍数 3 都没意义了
O (nlogN)
O (n^2)
因为 n 趋近于无限大，所以 n 相对于 n ^2 就是一个常量
O (nm)
三种复杂度
最坏时间复杂度
考虑输入数据“最好”的情况平均时间复杂度
考虑所有输入数据都等概率出现的情况最好时间复杂度
考虑输入数据“最好”的情况
空间复杂度
空间开销（内存开销）与问题规模 n 之间的关系如何计算
普通程序
找到所占空间大小与问题规模相关的变量
分析所占空间 x 与问题规模 n 的关系 x = f(n)
x 的数量级 O (x) 就是算法空间复杂度 S(n)
递归程序
找到递归调用的深度 x 与问题规模 n 的关系 x = f(n)
x 的数量级 O (x) 就是算法空间复杂度 S(n)
注：有的算法各层函数所需的存储空间不同，分析方法略有区别
常用技巧
加法法则：O (f(n)) + O(g(n)) = O (max(f(n),g(n)))
乘法法则：O(f(n)) x O(g(n)) = O(f(n) x g(n))
记忆技巧：常对幂指阶
O (1)
需要的空间是一个常数量
O (n)
经过 for 循环，数组里面就会有值，如果往数组里面添加越多的数据，则需要更多的空间内存等
O (n^2)
- 矩阵（二维数组）
其他复杂度指标
