1 00:00:04,966 --> 00:00:05,860 大家好 2 00:00:05,934 --> 00:00:10,632 数据结构与算法这一讲我们继续学习第一章概论 3 00:00:10,712 --> 00:00:16,275 我们今天的内容主要是介绍算法的特性以及它的简单分类 4 00:00:17,333 --> 00:00:22,563 算法在计算机的问题求解当中起着非常重要的作用 5 00:00:23,311 --> 00:00:28,589 我们计算机的一个问题其实是一个函数 6 00:00:28,669 --> 00:00:34,427 它把一定的输入数据映射到相应的输出结果 7 00:00:34,500 --> 00:00:37,028 而这个映射的过程就是算法 8 00:00:37,642 --> 00:00:43,728 算法是由一些具体的有效的序列组成的 9 00:00:44,200 --> 00:00:56,563 而这个序列在计算机的环境当中,我们必须把它实现为具体的程序用一种计算机程序设计语言来编写 10 00:00:56,660 --> 00:01:10,350 然后在特定的操作系统环境下用特定的编译器来把它翻译为机器可理解执行的二进制代码最后来完成这个问题的求解 11 00:01:13,128 --> 00:01:16,959 算法它有一些相关的特性 12 00:01:17,031 --> 00:01:26,640 首先它需要有通用性,也就是说我们编写算法,是为了反复的去求解同一类问题的 13 00:01:26,715 --> 00:01:48,808 例如对于这么一个八皇后问题,也就是说在8×8的棋盘格上,我们放置8个皇后,然后每一行每一列以及对角线这些皇后都互相不能攻击,也就是在同行同列同对角线上,不能有两个以上的皇后 14 00:01:49,567 --> 00:01:59,794 八后问题,其实我们也可以说四后问题或者是n后问题,它的解决方案其实是类似的 15 00:01:59,891 --> 00:02:06,587 我们只是把这个n后呢进行了一个参数化,我们说是n后问题 16 00:02:08,262 --> 00:02:15,584 如果我们编写了有效的算法,我对同一类的问题都是能够进行正确的求解的 17 00:02:16,642 --> 00:02:20,933 另外我们还有一个特性就是有效性 18 00:02:21,029 --> 00:02:25,297 编写算法的目的是为了进行问题求解 19 00:02:25,370 --> 00:02:28,336 问题求解它是有意义的 20 00:02:28,432 --> 00:02:39,938 我们通过一个有效的算法,编写有限有序的序列,然后把这个问题求解出来的 21 00:02:41,100 --> 00:02:44,047 我们的结果应该是有效的 22 00:02:44,135 --> 00:02:46,701 我们的过程也是有效的 23 00:02:48,492 --> 00:02:50,414 算法还有一个确定性 24 00:02:50,498 --> 00:03:00,063 那就是说在编写算法的过程中其实我们每一个算法步骤都是明确的 25 00:03:00,152 --> 00:03:05,890 当程序执行到这个地方的时候,我会有一个数据的环境 26 00:03:07,505 --> 00:03:17,407 我下一步该做什么,一定是能够通过当前输入的数据得到下一步应该进行什么样的处理的信息 27 00:03:18,062 --> 00:03:33,702 举例来说,对于if else这么一个判断 28 00:03:23,081 --> 00:03:25,865 我如果得到了数据,那么我一定是知道下面是进then还是进else,不会说随机分配一个进入 29 00:03:33,782 --> 00:03:49,657 当然在某些情境下,例如人工智能的模糊系统等等这些判断下,你看起来似乎是不那么确定或者还有一些随机的算法是进行随机选择的 30 00:03:49,745 --> 00:03:56,271 但是在我们编写出代码以后,我得到什么样的数据就会进行什么样的判断 31 00:03:56,351 --> 00:03:57,738 它其实是不随机的 32 00:03:57,810 --> 00:04:00,869 也就是说在底层来看,它是非常具体的 33 00:04:01,546 --> 00:04:03,783 另外算法还有一个有穷性 34 00:04:04,451 --> 00:04:11,840 也就是说算法应该是在确定的时间内用确定的步骤来完成的 35 00:04:12,990 --> 00:04:19,557 我们不可能编写一个无限循环的算法,永远得不到结果 36 00:04:19,645 --> 00:04:29,232 当然我们常用的操作系统,它其实本质上就是一个死循环的程序 37 00:04:29,640 --> 00:04:40,607 它不断地等待着外界的指令比如说键盘或者鼠标这些事件然后它再进行相应的操作 38 00:04:42,803 --> 00:04:49,768 从算法的意义来说操作系统它就不是一个算法因为它本身是一个死循环的程序 39 00:04:50,685 --> 00:04:54,898 我们来看皇后问题的一个例子 40 00:04:56,919 --> 00:05:14,183 对于这样的一个4皇后的情况,因为对同行的皇后我们是不能摆2个以上的,因此我就假设这个解就是一个4元组 41 00:05:14,247 --> 00:05:20,870 它表示的是每一行的皇后它所处的列的值 42 00:05:20,949 --> 00:05:27,669 因为每一列不能有2个以上的皇后,因此这其实就是一个排列 43 00:05:28,817 --> 00:05:34,240 对于4皇后问题的所有的排列情况,我们把它列举出来 44 00:05:34,312 --> 00:05:36,212 其实我们就得到了这么一个4叉树 45 00:05:38,798 --> 00:05:48,756 这个4叉树是按照第一行是放1还是2 3 4而分成4个分支的 46 00:05:49,180 --> 00:05:54,592 然后接着再去看第二行可以在哪些列上放置相应的皇后 47 00:05:54,682 --> 00:05:59,259 我们就这样得到了这么一个4叉树的搜索空间 48 00:06:00,897 --> 00:06:15,632 对于这个4后问题,如果我没有很好的解法,那么我就是对这个搜索空间进行一个判断,把那些不合法的解也就是对角线上冲突了的这些解给它去掉 49 00:06:16,121 --> 00:06:17,554 我们最后就得到两组解 50 00:06:19,938 --> 00:06:22,141 这是红色标出来的两组解 51 00:06:22,230 --> 00:06:25,366 这两组解,我们可以看到它其实是对称的 52 00:06:26,554 --> 00:06:28,521 我们可以有一些算法对它进行更优的求解 53 00:06:32,024 --> 00:06:38,171 也就是说有一些分支其实我们不用去看就能判断它肯定是没有解的 54 00:06:38,244 --> 00:06:53,732 例如如果我第一行把皇后摆在第一列,第二行我要把它摆在第二列,这种情况下对角线冲突了所以整个分支就不需要再继续去查看了 55 00:06:54,825 --> 00:07:00,583 这样的一个求解的过程其实就是我们的回溯思想 59 00:07:00,639 --> 00:07:13,128 回溯算法可以大大的缩减我们求解的时间因为我们在搜索空间上可以得到很大的简化 60 00:07:13,817 --> 00:07:26,341 这个皇后问题的左半部分我们标出了蓝色的这些路径就是我们可能的搜索路径 61 00:07:26,413 --> 00:07:30,730 右半部分是跟它对称的我们就没有再标出来了 62 00:07:31,429 --> 00:07:34,905 我们来看算法的简单分类 63 00:07:35,425 --> 00:07:36,985 对于所有的问题我们在没有很好的算法来求解的情况下我们都可以考虑穷举法的方法 64 00:07:44,619 --> 00:07:54,951 首先看一下这个问题有什么特性,它的数据有什么特性,然后再看看有没有可能用更高效的解法来求解 65 00:07:55,039 --> 00:08:06,100 例如我们刚才这个4后问题,在开始的时候我们可以用穷举法把所有的这些解给它罗列出来 66 00:08:06,164 --> 00:08:11,801 然后我再用回溯的方法来进行有效的搜索 67 00:08:11,865 --> 00:08:21,586 回溯的思想实际上是一个能进则进,不能进我就换,不能换我再退的这么一个过程 68 00:08:23,927 --> 00:08:35,400 在数据结构与算法当中树和图的遍历以及很多问题的求解的过程其实都是用的回溯搜索的思想 69 00:08:36,081 --> 00:08:39,351 还有一类方法就是递归分治 70 00:08:39,943 --> 00:08:48,600 递归分治方法对于一些特定的问题有比较好的求解方法 71 00:08:49,784 --> 00:09:03,224 例如我们如果要在一个有序的数组已经排好序的情况下在里面去找K值,就可以用二分的方法进行递归的求解 72 00:09:04,102 --> 00:09:08,893 贪心法是一种特殊的算法 73 00:09:08,973 --> 00:09:15,259 它的数据有一些比较特定的情况也就是有贪心性质 74 00:09:15,331 --> 00:09:20,754 我们在每次求解的时候都去看当前的最佳解 75 00:09:20,833 --> 00:09:28,390 我每次贪心求最佳然后最后得到的总体的结果也是最佳的 76 00:09:29,703 --> 00:09:35,588 在我们教材里面有一些算法是贪心的方法 77 00:09:37,057 --> 00:09:53,712 动态规划的方法是对于小规模的问题我们得到最优解,然后我在更大规模的时候去组合这些最优解,最后对于整个大问题我们得到一个整体的最优解 78 00:09:53,792 --> 00:10:00,730 而动态规划方法要求有最优子结构性质,无后效性 79 00:10:01,455 --> 00:10:03,247 它的子结构其实是有重叠子结构 80 00:10:06,193 --> 00:10:09,281 我们来看一个穷举法的例子 81 00:10:10,020 --> 00:10:15,284 在一个无序的数组里面我们要查找K这个元素 82 00:10:17,487 --> 00:10:25,452 因为没有任何的线索,我们只能够挨个去找因此它就是一个穷举的过程 83 00:10:26,188 --> 00:10:36,047 对于这个算法,我们把数组的第0位给它空出来当做监视哨存放的就是我们待找的这个K值 84 00:10:36,623 --> 00:10:38,743 我们从数组的最后一个元素挨个往前找 85 00:10:40,086 --> 00:10:45,604 如果在中间找到了这个元素,我们就返回它相应的下标 86 00:10:46,528 --> 00:10:51,590 如果一直找到第0位我们也会停止 87 00:10:51,662 --> 00:10:58,978 因为第0位就是我们要的这个K值,我们提前把它放作监视哨了 88 00:10:59,051 --> 00:11:12,190 在这里设置监视哨的作用就是我们在查找的过程中不需要判断这个下标i是不是越过了数组的下界 89 00:11:13,344 --> 00:11:18,886 少了一个判断我们算法的运行效率会更高一些 90 00:11:19,731 --> 00:11:25,481 我们再来看一个更高效的递归分治找K值的方法 91 00:11:26,885 --> 00:11:38,068 这个算法的前提是我们要对数组进行一个排序。排序了以后,我就能够更快捷的去找K值 92 00:11:39,654 --> 00:11:47,358 在数组的中间找到这个元素,然后我们跟K值进行比较 93 00:11:47,433 --> 00:11:49,657 如果是相等那我们就结束了 94 00:11:49,749 --> 00:11:55,788 如果是这个中间元素比K值要小那我们就要在右半边继续找 95 00:11:55,884 --> 00:12:00,693 如果中间元素比K值要大那我就在左半边继续找 96 00:12:00,764 --> 00:12:09,310 不管怎么样我如果查找失败,总是会缩小一半的规模再继续找 97 00:12:09,397 --> 00:12:12,615 因此这是一个非常高效的算法 98 00:12:14,419 --> 00:12:17,219 我们来看二分找K值的算法 99 00:12:17,283 --> 00:12:25,613 首先我们传入了这个数组以及它的长度还有就是我们待找的这个k 100 00:12:25,700 --> 00:12:34,446 我设置整个查找区间的下界和上界分别是位置1和数组长度 101 00:12:36,871 --> 00:12:39,907 我们还是把第0位给空出来 102 00:12:39,983 --> 00:12:50,305 我们得到中间位置标号mid,然后我们把k值跟mid位置的数值进行比较 103 00:12:50,395 --> 00:12:52,687 如果相等那我们就返回mid 104 00:12:53,319 --> 00:13:06,365 如果k小于mid这个位置的数值,我们就会在左半边继续找并把上界取为刚才那个mid再减1的位置 105 00:13:10,493 --> 00:13:21,101 反过来如果k值大于中间位置那个数值,我们就会在右半边找并把low取为mid+1 106 00:13:22,660 --> 00:13:37,082 如果一直到low小于high,还不能够满足,也就是说出现下界超过上界这种情况,说明查找失败返回数值0 107 00:13:37,691 --> 00:13:40,401 也就是不在有效的1到length这个数据范围之内,也就是检索失败 108 00:13:47,155 --> 00:13:50,551 我们看一下二分法检索的图示 109 00:13:50,615 --> 00:13:57,275 我们设置下标low和high,它们是下界和上界 110 00:13:58,330 --> 00:14:02,157 mid就是它们的中位就是5 111 00:14:02,245 --> 00:14:04,382 我们要找的元素是18 112 00:14:04,453 --> 00:14:10,446 18比5这个位置的值35要小 113 00:14:10,517 --> 00:14:20,087 因此我们把这个上界缩到mid的左边mid-1然后我们在左半侧继续找 114 00:14:20,733 --> 00:14:26,648 现在左半侧的中位值是17,比18要小 115 00:14:26,736 --> 00:14:30,820 因此我们在查找区间的右半边继续找 116 00:14:31,368 --> 00:14:42,949 现在这个右半边的中位是3,这个位置的值是18,那我们就找到了我们待检索的数据 117 00:14:44,345 --> 00:14:54,186 我们刚才看到的这个过程是非常快速就能完成比我们前面穷举法挨个去找是要高效很多了 118 00:14:56,018 --> 00:14:58,619 我们让大家思考一下 119 00:14:59,307 --> 00:15:07,620 一个算法要求你将数组的元素循环右移k位 120 00:15:08,905 --> 00:15:27,472 比如说这样的一个原始的数组有0-9这10个元素,我要求循环右移3位,那就是这个0元素到了我们原来位置后面3个位置的地方 121 00:15:27,544 --> 00:15:32,468 它跳了3位,那也就是把前面的789给折过来了 122 00:15:33,034 --> 00:15:37,055 我们得到这么一个新的数组 123 00:15:37,933 --> 00:15:41,319 这个算法还有时间和空间的限制 124 00:15:41,391 --> 00:15:50,423 所谓空间限制就是你在做这个操作的过程中只能用一个辅助的变量 124 00:15:50,493 --> 00:15:56,553 这个变量的大小限制为数组元素大小 125 00:15:58,842 --> 00:16:12,396 还有它的时间限制就是你在移动的过程中不管是移动也好或者是交换也好它的这个总的次数只能是跟n线性相关 126 00:16:12,836 --> 00:16:18,661 也就是说你不能够达到一个n平方规模的的算法 127 00:16:19,309 --> 00:16:24,569 在这样的限制之下你怎么样来考虑这个算法的设计 128 00:16:25,791 --> 00:16:35,339 这个问题其实就引入了我们下一讲算法的时间和空间的效率分析的问题 129 00:16:35,979 --> 00:16:36,771 谢谢大家