算法的时间和空间性能非常重要
一、算法的渐近分析 当 n 增大到一定值后，其他的常数项和低幂次项都可以忽略，只需确定是在什么量级（线性、n 方、指数级等）
1. 大 $\mathcal{O}$ 表式法 函数增长率上限
2. 大 $\Omega$ 表式法 函数增值率的下限
3. 大 $\Theta$ 表示法 当上、下限相同时则可用 $\Theta$ 表示法
二、增长率曲线 三、数据结构和算法的选择 仔细分析所要解决的问题 特别是求解问题所涉及的数据类型和数据间逻辑关系（问题抽象、数据抽象） 数据结构的初步设计往往先于算法设计 注意数据结构的可扩展性 考虑当输入数据的规模发生改变时，数据结构是否能够适应求解问题的演变和扩展 三、思考题 数据结构的三个要素任何一个发生改变，都是不同的数据结构，请举例讨论
双向链表和二叉树的存储结构其实是一样的，他们的不同在于逻辑结构。 数组和向量都是线性表，其存储形式不同，成为不同的数据结构。 算法设计目标是什么？
时间和空间的权衡 易读 易编码 易调试 易维护 易扩展 算法选择的过程？
要求在时间复杂度 $\mathcal{O}(n)$、空间复杂度 $\mathcal{O}(1)$，使数组元素循环向右移动 K 位
一、问题——算法——程序 问题：一个函数，从输入到输出在一种映射 算法：对特定问题求解过程的描述，是指令的有限序列 程序：算法在计算机程序设计语言中的具体实现 二、算法的特性 通用性：参数化的，能对一类问题进行参数化输入并问题求解 有效性：有限条有效指令组成的指令序列，保证计算结果的正确性 确定性：算法的下一步执行步骤必须明确 有穷性：执行必须在有限步内结束，不能有死循环 三、基本算法分类 穷举法：
遍历每一个元素，比较低效，但是是一种万能的算法；对于一个问题，如果一时想不出好的算法的话，可对小规模数据采用穷举法剖析问题的特性和数据的特性，进而寻求更高效的算法 回溯、搜索：
能进则进，不能进则换，不能换则退，如树和图的遍历 递归分治：
二分查找，以及快速排序、归并排序，都是经典的分治算法思想 贪心法：
其数据具有贪心性质，每次求解的时候都采用当前的最佳解，最终得到最优解，如 Huffman 编码树、最短路径 Dijkstra 算法、最小生成树 Prim 算法 动态规划：
得到小规模问题的最优解，然后在更大规模的时候去组合这些最优解，最后得到全局的最优解，如图的两两结点之间最短路 Floyd 算法。要求具有最优子结构性质以及无后效性，动态规划的子结构有重叠，而递归分治子结构不重叠。 四、“监视哨”顺序检索 设置“监视哨”后，在查找过程中不用判断 i 是否越界，少一次判断，算法的运行效率会更高
一、什么是数据结构 结构：实体 + 关系，比如分子结构，关系图等
数据结构：按照逻辑关系组织起来的一批数据，按一定的存储方法所把它存储在计算机中，并在这些数据上定义了一个运算的集合
二、数据的逻辑结构 线性结构
线性表（表、栈、队列、串等） 非线性结构
树（二叉树、Huffman树、二叉检索树等）
图（有向图、无向图等） 图 ⊇ 树 ⊇ 二叉树 ⊇ 线性表 三、数据的存储结构 将逻辑结构的结点映射到内存中，每一个结点都对应一个唯一的连续存储区域
内存可以看作从低地址到高地址的一个编码的线性结构，可以根据地址立即访问想要访问的内存单元，不需要搜索
存储结构主要有顺序、链接、索引和散列四种形式
顺序存储对应于数组 链接存储对应于链表 索引是对数据建立一个索引表，通过这个表有效的找到相应数据的存储地址 散列是一种特殊的索引结构，本身也是一种存储结构，通过关键码的映射关系，在整个散列表中用单位时间快速地找到其存储地址 四、抽象数据类型 ADT（Abstract Data Type） 定义了一组运算的数学模型 与物理存储结构无关 使软件系统建立在数据之上(面向对象) 五、定义抽象数据类型 抽象数据类型就是在逻辑结构上的运算，可以理解为抽象数据结构二元组 <数据对象D, 数据操作P>
先定义逻辑结构，再定义运算
逻辑结构：数据对象及其关系 运算：数据操作 就像面向对象语言中所定义的类（特别是抽象类），封装了数据成员和函数成员
算法 + 数据结构 = 程序 数据结构与算法是程序的灵魂，以问题求解为导向，进行问题抽象、数据抽象、算法抽象，通过有效地组织数据、设计高效的算法、完成高质量的程序，从而解决实际应用的问题。
流程：问题 => 数据 => 算法
理论（离散数学、概率统计、图论等） => 抽象（问题抽象、数据抽象、算法抽象等面向对象思想） => 设计（实现的某种具体编程语言）
逻辑抽象 + 运算抽象 => ADT
运算 + 存储 => 算法分析（时间和空间复杂度）
问题抽象：分析和抽象任务需求，建立问题模型
数据抽象：确定恰当的数据结构表示数学模型
算法抽象：在数据模型的基础上设计合适的算法
哈希表及处理冲突的方法
一、哈希法与哈希表 哈希法又称散列法、杂凑法以及关键字地址计算法等，相应的表称为哈希表。 这种方法的基本思想是：首先在元素的关键字 k 和元素的存储位置 p 之间建立一个对应关系 f，使得 p = f(k)，f 称为哈希函数。 创建哈希表时，把关键字为 k 的元素直接存入地址为 f(k) 的单元；以后当查找关键字为 k 的元素时，再利用哈希函数计算出该元素的存储位置 p=f(k)，从而达到按关键字直接存取元素的目的。 二、冲突 当关键字集合很大时，关键字值不同的元素可能会映象到哈希表的同一地址上，即 k1 ≠ k2，但 f(k1) = f(k2)，这种现象称为冲突，此时称 k1 和 k2 为同义词。
三、哈希函数构造方法 构造哈希函数的原则是：
函数本身便于计算； 计算出来的地址分布均匀，即对任一关键字 k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突 常用的构造方法：
数字分析法 平方取中法 分段叠加法 除留余数法：假设哈希表长为 m，p 为小于等于 m 的最大素数，则哈希函数为 f(k)=k % p 伪随机数法 四、冲突处理方法 1. 开放地址法（Open addressing） 这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi
线性探测 二次探测 伪随机探测 线性探测再散列的优点是：只要哈希表不满，就一定能找到一个不冲突的哈希地址，而二次探测再散列和伪随机探测再散列则不一定；缺点是线性探测再散列容易产生二次聚集
2. 再哈希法 这种方法是同时构造多个不同的哈希函数，当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间...