文章目录
- 1. 逻辑结构和存储结构
- 2. 算法
- 3. 算法效率度量
- 3.1 算法时间复杂度
- 3.2 算法空间复杂度
1. 逻辑结构和存储结构
逻辑结构四种基本结构：集合结构、线性结构、树形结构、图形结构（对人友好）
存储结构分类：顺序存储、链式存储、索引存储、散列存储（对计算机友好）
- 顺序存储：逻辑上相邻的元素在物理位置上也相邻
- 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系
- 索引存储：在存储信息的同时，还建立附加的索引表
- 散列存储：根据元素的关键字直接计算出该元素的存储地址
顺序存储和链式存储分析：
-
顺序存储优点：
-
- 可以实现随机存储
-
- 每个元素占用最少的空间
-
-
链式存储优点：充分利用所有存储单元，不会出现碎片现象
-
顺序存储缺点：只能使用整块的存储单元，会产生较多的碎片
-
链式存储缺点：
- 1.需要额外的存储空间用来存放下一结点的指针。
- 2.只能实现顺序存取
2. 算法
数据结构：相互之间存在一种或多种特定关系的数据元素的集合
算法：是对特定问题求解步骤的一种描述
算法五个特性：有穷性、确定性、可行性、输入输出性
- 有穷性：算法必须是有穷的，即每一步在有穷的时间内完成，而程序可以是无穷的（例如微信是程序，不是算法）
- 确定性：每条指令都必须有确切的含义，对于相同的输入只能得到相同的输出。
- 可行性：给出的实现方案必须能用计算机代码实现。
- 输入：一个算法有零个或者多个输入，这些输入取自于某个特定对象的集合
- 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量
好的算法特质：正确性、可读性、健壮性（输入非法数据，可以对其进行处理）、高效率和低存储需求
3. 算法效率度量
3.1 算法时间复杂度
事先预估算法时间开销T（n）与问题规模n的关系（T代表time）
简化时间复杂度表达式：
当问题规模n足够大的时候，只需要保留阶数高的部分
分析时间复杂度两条规则：
常见的渐近时间复杂度：（常对幂指阶）
最坏时间复杂度：考虑输入数据‘最坏’的情况
平均时间复杂度：考虑所以输入数据都等概率出现的情况
最好时间复杂度：考虑输入数据‘最好’的情况
3.2 算法空间复杂度
描述一个算法所需的存储空间，用S（n）来表示，它是规模为n的函数（S表示“space”）
1.无论问题规模这么变，算法运行所需的内存空间都是固定的常数，算法的空间复杂度为S(n)=O(1)
算法原地工作：算法所需内存空间为常量
2.找到所占空间与问题规模相关的变量，分析所占空间x与问题规模n的关系 x=f（n）,x的数量级O(x)就是算法空间复杂度S(n)
3.递归函数的空间复杂度跟函数调用的深度有关
