大家好
数据结构与算法这一讲我们继续学习第一章概论
我们今天的内容主要是介绍算法的特性以及它的简单分类
算法在计算机的问题求解当中起着非常重要的作用
我们计算机的一个问题其实是一个函数
它把一定的输入数据映射到相应的输出结果
而这个映射的过程就是算法
算法是由一些具体的有效的序列组成的
而这个序列在计算机的环境当中，我们必须把它实现为具体的程序用一种计算机程序设计语言来编写
然后在特定的操作系统环境下用特定的编译器来把它翻译为机器可理解执行的二进制代码最后来完成这个问题的求解
算法它有一些相关的特性
首先它需要有通用性，也就是说我们编写算法，是为了反复的去求解同一类问题的
例如对于这么一个八皇后问题，也就是说在8×8的棋盘格上，我们放置8个皇后，然后每一行每一列以及对角线这些皇后都互相不能攻击，也就是在同行同列同对角线上，不能有两个以上的皇后
八后问题，其实我们也可以说四后问题或者是n后问题，它的解决方案其实是类似的
我们只是把这个n后呢进行了一个参数化，我们说是n后问题
如果我们编写了有效的算法，我对同一类的问题都是能够进行正确的求解的
另外我们还有一个特性就是有效性
编写算法的目的是为了进行问题求解
问题求解它是有意义的
我们通过一个有效的算法，编写有限有序的序列，然后把这个问题求解出来的
我们的结果应该是有效的
我们的过程也是有效的
算法还有一个确定性
那就是说在编写算法的过程中其实我们每一个算法步骤都是明确的
当程序执行到这个地方的时候，我会有一个数据的环境
我下一步该做什么，一定是能够通过当前输入的数据得到下一步应该进行什么样的处理的信息
举例来说，对于if else这么一个判断
我如果得到了数据，那么我一定是知道下面是进then还是进else，不会说随机分配一个进入
当然在某些情境下，例如人工智能的模糊系统等等这些判断下，你看起来似乎是不那么确定或者还有一些随机的算法是进行随机选择的
但是在我们编写出代码以后，我得到什么样的数据就会进行什么样的判断
它其实是不随机的
也就是说在底层来看，它是非常具体的
另外算法还有一个有穷性
也就是说算法应该是在确定的时间内用确定的步骤来完成的
我们不可能编写一个无限循环的算法，永远得不到结果
当然我们常用的操作系统，它其实本质上就是一个死循环的程序
它不断地等待着外界的指令比如说键盘或者鼠标这些事件然后它再进行相应的操作
从算法的意义来说操作系统它就不是一个算法因为它本身是一个死循环的程序
我们来看皇后问题的一个例子
对于这样的一个4皇后的情况，因为对同行的皇后我们是不能摆2个以上的，因此我就假设这个解就是一个4元组
它表示的是每一行的皇后它所处的列的值
因为每一列不能有2个以上的皇后，因此这其实就是一个排列
对于4皇后问题的所有的排列情况，我们把它列举出来
其实我们就得到了这么一个4叉树
这个4叉树是按照第一行是放1还是2 3 4而分成4个分支的
然后接着再去看第二行可以在哪些列上放置相应的皇后
我们就这样得到了这么一个4叉树的搜索空间
对于这个4后问题，如果我没有很好的解法，那么我就是对这个搜索空间进行一个判断，把那些不合法的解也就是对角线上冲突了的这些解给它去掉
我们最后就得到两组解
这是红色标出来的两组解
这两组解，我们可以看到它其实是对称的
我们可以有一些算法对它进行更优的求解
也就是说有一些分支其实我们不用去看就能判断它肯定是没有解的
例如如果我第一行把皇后摆在第一列，第二行我要把它摆在第二列，这种情况下对角线冲突了所以整个分支就不需要再继续去查看了
这样的一个求解的过程其实就是我们的回溯思想
回溯算法可以大大的缩减我们求解的时间因为我们在搜索空间上可以得到很大的简化
这个皇后问题的左半部分我们标出了蓝色的这些路径就是我们可能的搜索路径
右半部分是跟它对称的我们就没有再标出来了
我们来看算法的简单分类
对于所有的问题我们在没有很好的算法来求解的情况下我们都可以考虑穷举法的方法
首先看一下这个问题有什么特性，它的数据有什么特性，然后再看看有没有可能用更高效的解法来求解
例如我们刚才这个4后问题，在开始的时候我们可以用穷举法把所有的这些解给它罗列出来
然后我再用回溯的方法来进行有效的搜索
回溯的思想实际上是一个能进则进，不能进我就换，不能换我再退的这么一个过程
在数据结构与算法当中树和图的遍历以及很多问题的求解的过程其实都是用的回溯搜索的思想
还有一类方法就是递归分治
递归分治方法对于一些特定的问题有比较好的求解方法
例如我们如果要在一个有序的数组已经排好序的情况下在里面去找K值，就可以用二分的方法进行递归的求解
贪心法是一种特殊的算法
它的数据有一些比较特定的情况也就是有贪心性质
我们在每次求解的时候都去看当前的最佳解
我每次贪心求最佳然后最后得到的总体的结果也是最佳的
在我们教材里面有一些算法是贪心的方法
动态规划的方法是对于小规模的问题我们得到最优解，然后我在更大规模的时候去组合这些最优解，最后对于整个大问题我们得到一个整体的最优解
而动态规划方法要求有最优子结构性质，无后效性
它的子结构其实是有重叠子结构
我们来看一个穷举法的例子
在一个无序的数组里面我们要查找K这个元素
因为没有任何的线索，我们只能够挨个去找因此它就是一个穷举的过程
对于这个算法，我们把数组的第0位给它空出来当做监视哨存放的就是我们待找的这个K值
我们从数组的最后一个元素挨个往前找
如果在中间找到了这个元素，我们就返回它相应的下标
如果一直找到第0位我们也会停止
因为第0位就是我们要的这个K值，我们提前把它放作监视哨了
在这里设置监视哨的作用就是我们在查找的过程中不需要判断这个下标i是不是越过了数组的下界
少了一个判断我们算法的运行效率会更高一些
我们再来看一个更高效的递归分治找K值的方法
这个算法的前提是我们要对数组进行一个排序。排序了以后，我就能够更快捷的去找K值
在数组的中间找到这个元素，然后我们跟K值进行比较
如果是相等那我们就结束了
如果是这个中间元素比K值要小那我们就要在右半边继续找
如果中间元素比K值要大那我就在左半边继续找
不管怎么样我如果查找失败，总是会缩小一半的规模再继续找
因此这是一个非常高效的算法
我们来看二分找K值的算法
首先我们传入了这个数组以及它的长度还有就是我们待找的这个k
我设置整个查找区间的下界和上界分别是位置1和数组长度
我们还是把第0位给空出来
我们得到中间位置标号mid，然后我们把k值跟mid位置的数值进行比较
如果相等那我们就返回mid
如果k小于mid这个位置的数值，我们就会在左半边继续找并把上界取为刚才那个mid再减1的位置
反过来如果k值大于中间位置那个数值，我们就会在右半边找并把low取为mid+1
如果一直到low小于high，还不能够满足，也就是说出现下界超过上界这种情况，说明查找失败返回数值0
也就是不在有效的1到length这个数据范围之内，也就是检索失败
我们看一下二分法检索的图示
我们设置下标low和high，它们是下界和上界
mid就是它们的中位就是5
我们要找的元素是18
18比5这个位置的值35要小
因此我们把这个上界缩到mid的左边mid-1然后我们在左半侧继续找
现在左半侧的中位值是17，比18要小
因此我们在查找区间的右半边继续找
现在这个右半边的中位是3，这个位置的值是18，那我们就找到了我们待检索的数据
我们刚才看到的这个过程是非常快速就能完成比我们前面穷举法挨个去找是要高效很多了
我们让大家思考一下
一个算法要求你将数组的元素循环右移k位
比如说这样的一个原始的数组有0-9这10个元素，我要求循环右移3位，那就是这个0元素到了我们原来位置后面3个位置的地方
它跳了3位，那也就是把前面的789给折过来了
我们得到这么一个新的数组
这个算法还有时间和空间的限制
所谓空间限制就是你在做这个操作的过程中只能用一个辅助的变量
这个变量的大小限制为数组元素大小
还有它的时间限制就是你在移动的过程中不管是移动也好或者是交换也好它的这个总的次数只能是跟n线性相关
也就是说你不能够达到一个n平方规模的的算法
在这样的限制之下你怎么样来考虑这个算法的设计
这个问题其实就引入了我们下一讲算法的时间和空间的效率分析的问题
谢谢大家