绪论
考纲内容：算法时间复杂度和空间复杂度的分析与计算
数据结构的基本概念
在任何问题中，数据元素都不是孤立存在的，它们之间存在某种关系，这种数据元素相互之间的关系称为结构（Structure）。
数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算。 数据的逻辑结构和存储结构是密不可分的两个方面，算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。
- 数据元素-item
- 数据对象-list
逻辑结构
分为2大类：线性结构与非线性结构
- 集合。结构中的数据元素之间除“同属一个集合”外，别无其他关系，如图1.2（a）所示。
- 线性结构（
线性表）。结构中的数据元素之间只存在一对一的关系，如图1.2（b）所示。 - 树形结构。结构中的数据元素之间
存在一对多的关系，如图1.2（c）所示。 - 图状结构或网状结构。结构中的数据元素之间
存在多对多的关系，如图1.2（d）所示。
存储结构
又称为物理结构，包括数据元素的表示和关系的表示。数据的存储结构是用计算机语言实现的逻辑结构，它依赖于计算机语言。数据的存储结构主要有顺序存储、链式存储、索引存储和散列存储。
- 顺序存储：逻辑上相邻的元素在物理位置上也相邻
- 优点：可以实现随机存储，每个元素占用最少的存储空间
- 缺点：可能产生较多的外部碎片
- 链式存储。不要求逻辑上相邻的元素在物理位置上也相邻，通过指针存储地址表示各个元素之间的逻辑关系
- 优点：不会出现碎片现象，能充分利用所有存储单元：
- 缺点：占用额外的存储空间，且只能实现顺序存取。
- 索引存储。在存储元素信息的同时，还建立附加的索引表
- 优点：检索速度快：
- 缺点：额外占用存储空间。C、D耗时
- 散列存储。根据元素的关键字直接计算出该元素的存储地址，又称哈希（Hash）存储。
- 优点：R、C、D很快
- 缺点：可能出现元素存储单元的冲突，而解决冲突会增加时间和空间开销。
INFO
注意思考逻辑结构与存储结构之间的差异：
- 存储结构是用计算机语言实现的逻辑结构
- 设计对应逻辑结构，实现对应物理结构
- 逻辑结构独立于物理结构
算法与算法评价
算法具有的特征：有穷性、确定性、可行性、输入、输出
时间复杂度
假设单行代码的执行时间为单位t，那么对于问题规模n，它的执行时间为nt。时间复杂度则是取一个算法中耗时最长（嵌套最深）的那块代码的执行次数 的数量级。
时间复杂度又可以分为：最坏、平均、最好，但是总是考虑最坏时间复杂度
常见时间复杂度排序：
INFO
简单记为：常对幂指阶
计算思路
计算时间复杂度的思路，题型可以分为两大类：
首先遵循两个原则：加法原则（适用平级）与乘法原则（适用嵌套）
- 循环：归根结底是计算循环中i与执行次数t的关系，计算出总的执行次数并取最大的数量级
已知n=f(i)，i=f(t)，那么可知t=f(n)
- n为问题规模
- i为循环变量
- t为执行次数
整体计算：适用于多层嵌套且内层嵌套的循环次数依赖上层嵌套
单个计算：多层嵌套之间的循环次数互不影响
- 递归
递归时只调用1次函数，则从底部往上推
递归时调用多次函数，则用递归树参考，每个节点的次数总和为时间复杂度
WARNING
注意递归结束时的条件，一般不会考带有变量的结束条件
出题方向
- 在循环控制条件上动手脚，循环条件相互依赖
- 递归：F(n) = F(n-1) + F(n-2)
空间复杂度
算法计算过程中需要的存储空间
拓展
