- 衡量程序运行的效率
| 时间复杂度 |
|---|
| 一个顺序结构的代码，时间复杂度是 O(1) |
| 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn) |
| 一个简单的 for 循环，时间复杂度是 O(n) |
| 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n) |
| 两个嵌套的 for 循环，时间复杂度是 O(n²) |
- 降低复杂度的方法
| 名称 | 说明 |
|---|---|
| 暴力解法 | 在没有任何时间、空间约束下，完成代码任务的开发。 |
| 无效作处理 | 将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。 |
| 时空转换 | 设计合理数据结构，完成时间复杂度向空间复杂度的转移。 |
- 栈和线性表的区别
| 栈和线性表的区别 | |
|---|---|
| 相同 | 1、增删查操作原理极为相似 2、时间复杂度完全一样 |
| 不同 | 1、栈只允许数据从栈顶进出 |
- 队列和线性表的区别
| 队列和线性表的区别 | |
|---|---|
| 相同 | 1、增删查操作原理极为相似 2、时间复杂度完全一样 |
| 不同 | 1、队列只允许数据头进尾出 |
- 设计哈希函数的方法
| 名称 | 说明 |
|---|---|
| 直接定制法 | 哈希函数为关键字到地址的线性函数。如，H (key) = a*key + b。 这里，a 和 b 是设置好的常数 |
| 数字分析法 | 假设关键字集合中的每个关键字 key 都是由 s 位数字组成（k1,k2,…,Ks），并从中提取分布均匀的若干位组成哈希地址 |
| 平方取中法 | 如果关键字的每一位都有某些数字重复出现，并且频率很高，我们就可以先求关键字的平方值，通过平方扩大差异，然后取中间几位作为最终存储地址 |
| 折叠法 | 如果关键字的位数很多，可以将关键字分割为几个等长的部分，取它们的叠加和的值（舍去进位）作为哈希地址 |
| 除留余数法 | 预先设置一个数 p，然后对关键字进行取余运算。即地址为 key mod p |
- 解决哈希冲突的方法
| 名称 | 说明 |
|---|---|
| 开放定址法 | 当一个关键字和另一个关键字发生冲突时，使用某种探测技术在哈希表中形成一个探测序列，然后沿着这个探测序列依次查找下去。当碰到一个空的单元时，则插入其中。常用的探测方法是线性探测法 |
| 链地址法 | 将哈希地址相同的记录存储在一张线性链表中 |
- 分治法的使用场景
| 分治法的使用场景 |
|---|
难度在降低，即原问题的解决难度，随着数据的规模的缩小而降低。这个特征绝大多数问题都是满足的 |
问题可分，原问题可以分解为若干个规模较小的同类型问题。这是应用分治法的前提 |
解可合并，利用所有子问题的解，可合并出原问题的解。这个特征很关键，能否利用分治法完全取决于这个特征 |
相互独立，各个子问题之间相互独立，某个子问题的求解不会影响到另一个子问题。如果子问题之间不独立，则分治法需要重复地解决公共的子问题，造成效率低下的结果 |
- 常见的排序算法
| 名称 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 冒泡排序 | 最好O(n)最坏O(n*n)平均O(n*n) |
O(1) |
| 插入排序 | 最好O(n)最坏O(n*n)平均O(n*n) |
O(1) |
| 归并排序 | 最好O(nlogn)最坏O(n*nlogn)平均O(nlogn) |
O(n) |
| 快速排序 | 最好O(n*logn)最坏O(n*n)平均O(n*logn) |
O(1) |
- 衡量排序算法的优劣的三个因素
| 名称 | 说明 |
|---|---|
| 时间复杂度 | 最好时间复杂度、最坏时间复杂度、平均时间复杂度 |
| 空间复杂度 | 如果空间复杂度为 1，也叫作原地排序 |
| 稳定性 | 排序的稳定性是指相等的数据对象，在排序之后，顺序是否能保证不变 |
- 动态规划的基本方法
| 名称 | 说明 |
|---|---|
| 分阶段 | 将原问题划分成几个子问题 |
| 找状态 | 选择合适的状态变量 Sk |
| 做决策 | 确定决策变量 uk |
| 状态转移方程 | 动态规划最重要的核心，即 sk+1= uk(sk) |
| 定目标 | 写出代表多轮决策目标的指标函数 Vk,n |
| 寻找终止条件 |
- 动态规划的基本概念
| 名称 | 说明 |
|---|---|
| 策略 | 每轮的动作是决策，多轮决策合在一起常常被称为策略 |
| 策略集合 | 通常会称所有可能的策略为策略集合 |
- 动态规划的特征
| 名称 | 说明 |
|---|---|
| 最优子结构 | 原问题的最优解所包括的子问题的解也是最优的 |
| 无后效性 | 某阶段的决策，无法影响先前的状态 |
关联
[[C 《C语言数据结构》实验报告]]