杂项-《重学数据结构与算法》重视方法论

WechatIMG8.jpeg

重学数据结构与算法.jpg

  • 衡量程序运行的效率
时间复杂度
一个顺序结构的代码,时间复杂度是 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
寻找终止条件
  • 动态规划的基本概念
名称 说明
策略 每轮的动作是决策,多轮决策合在一起常常被称为策略
策略集合 通常会称所有可能的策略为策略集合
  • 动态规划的特征
名称 说明
最优子结构 原问题的最优解所包括的子问题的解也是最优的
无后效性 某阶段的决策,无法影响先前的状态
-------------本文结束感谢您的阅读-------------
0%