算法基础笔记
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法基础笔记,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4134字,纯文字阅读大概需要6分钟。
内容图文
![算法基础笔记](/upload/InfoBanner/zyjiaocheng/644/5191409aedd34cbca70a5c92cdd24b9d.jpg)
枚举
- 背景
- 找不到合适的数学公式和技巧
- (改良后)枚举复杂度不是特别大
- 通常用于找到一种情况使之满足题意的题目
- 配合假设法找到目标情形:假币问题
- 技巧
- 跳跃枚举法:跳过对没有必要的情况的枚举
- 局部枚举法:枚举局部,剩下的由该局部确定。例如熄灯问题
# 递归
- 作用
- 替代多重循环,如:n皇后问题。
- 这种类型往往要运用到一个==全局/静态变量==来存储前面算过的结果,譬如n皇后就用到了一个全局数组来保存每一行的皇后拜访情况。全局/静态变量的好处就在于==所有递归函数共享成果==,就像==递推迭代==一样,每一步会影响下一步。
- 递归函数形式:T function( T f(n) ),函数意义:在前n-1步已经完成的情况下决定如何走第n步,往往第一个被调用的function参数为0或1(然后依次调用1~n0)
- 解决实质是递归形式的问题
- 有些问题本身就是==递归定义==的,比如不少表达式就是递归定义的:逆波兰,四则运算。逆波兰==直接递归==调用自身定义,四则运算则包含项,因子和表达式自身等多个概念,是一种==间接递归==调用自身定义
- 函数,数列的递推公式
- 关键是搞清楚问题是怎样递归定义的,可以借助画图,写代数式的办法捋清楚。
- 将问题分解为规模更小的子问题来求解
- 如何来分解?
- ==“n=1+(n-1)”法==
- 比方说要解决一个规模为n的问题,先找到解决该问题的==第一步==怎么做,然后再把剩下的问题解决,剩下的问题规模刚好是n-1且解决过程自相似,可以用上递归n-1。e.g.台阶问题
- ==“n=(n-1)+1”法==
- 先解决n-1问题,再将最后一步完善,e.g.汉诺塔问题
- 与多重循环不同,该方法第一个调用的function参数往往时n0总规模
- 与分治不同,分治往往偏向于均分,而且多了一步综合,不过分治与递归又可以相互补充
- 替代多重循环,如:n皇后问题。
附注
- atof()函数,将浮点串转变为浮点数
- cin.peek()函数,提前预知输入而非读取
- 浮点数的比较引入eps
分治
- 基本思想
- 将一个问题拆分成两个或两个以上规模更小的问题,然后将小问题分别解决或只解决==部分==问题,最后==综合处理==一次。
- 一般模式:分划,局部处理,综合处理(分治 | 归并)
- 常常与==递归==思想结合
- 作用:使==规模缩小==,提高算法效率(想想:不断地递归并分治,使得规模不断二分)
- 应用举例:基于分治策略的快速排序和归并排序
附注
- " x & 1 " 表达式判别x奇偶性
- 快速幂算法
动态规划
- 背景
- 问题具有最优子结构
- 问题的最优解所包含的子问题的解也是最优的
- 问题具有无后效性
- 当前的若干个状态值一旦确定,则此后过程的演变就只和这若干个状态的值有关,和之前是采取何种手段或经过哪条路径演变到当前的这若干个状态,没有关系。
- 问题具有最优子结构
- 思路方法
- 原问题分解为子问题
- 一些问题的求解归结于它的子问题的求解,且子问题与原问题类似,只是规模减小。
- 子问题一旦解决即被保存(通常存入一个多维数组)。
- 确定状态
- “状态”简介:在用动态规划解题时,我们往往将和子问题相 关的各个变量的==一组取值==,称之为一个“==状态==”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“==值==”,就是这个“状态”所对应的==子问题的解==。
- ==状态空间与时间复杂度==:整个问题的时间复杂度是状态数目乘以计算每个状态所需时间。(在数字三角形里每个“状态”只需要经过一次,且在每个状态上作计算所花的时间都是和N无关的常数。)
- 用动态规划解题,经常碰到的情况是,K个整型变量能 构成一个状态(如数字三角形中的行号和列号这两个变量 构成“状态”)。如果这K个整型变量的取值范围分别是 N1, N2, ……Nk,那么,我们就可以用一个K维的数组 array[N1] [N2]……[Nk]来存储各个状态的“值”。这个 “值”未必就是一个整数或浮点数,可能是需要一个结构 才能表示的,那么array就可以是一个结构数组。一个 “状态”下的“值”通常会是一个或多个子问题的解。
- 确定一些初始状态(边界状态)的值
- 确定状态转移方程
- 将第一步 分解 得到的原问题与子问题的关系用数学符号语言表述出来,即实现状态之间的转移关系。
- 原问题分解为子问题
- 动规程序写法
- 记忆递归型
- 递归函数+记忆数组
- “人人为我”递推型
- 1,2,3,...,n-1 => n
- 递推到“n”时“n”仍未被求出,前面已被求出的状态值用于求“n”的状态值
- “我为人人”递推型
- n => k (k>n)
- 递推到“n”时“n”已经被求出,n将用于求后面的状态值
- 记忆递归型
动规中递归法向递推法转化的一般方法:
- 递归函数有n个参数,就定义一个n维的数组,数组 的下标是递归函数参数的取值范围,数组元素的值 是递归函数的返回值,这样就可以从边界值开始, 逐步填充数组,相当于计算递归函数值的逆过程。
常见分解(状态转移)方法归纳
- 多分类讨论, 想想解决原问题等同于解决什么和什么。有时候要经过多层分解才能够得到与原问题结构相同的子问题。
- “n=(n-1)+1”型与"n=1+(n-1)"型(与 递归 的 先走一步 思想又异曲同工之妙,n为问题规模)
- "F(i,j,k)=F(i-1,j,k)+F(i,j-1,k)+F(i,j,k-1)"型(这里拿 三维 的情况举例,其他维度的状态转移方程与此大同小异)
- "F(m,n)=A, A=G( F(m-1,n),F(m,n-1) )"型,间接递归
附注
- 数字三角形题目启示录:
①空间优化:滚动数组(通过覆盖今后无用的旧有数据空间的方法来压缩空间),降维,关注不必要的存储空间以及运行过程中变得可以丢弃的数据。②递归化递推:逆向思维。
内容总结
以上是互联网集市为您收集整理的算法基础笔记全部内容,希望文章能够帮你解决算法基础笔记所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。