第九章算法
第九章 算法
金部章 CONTENTS 9.1 算法简介 9.2 穷举算法 主要内容：算法的表示 主要内容：百元百鸡 算法运行时间 旅行商问题 9.3 查找算法 9.4 排序算法 主要内容：顺序查找 二分查找 主要内容：直接插入排序 选择排序 冒泡排序 快速排序
9.1 算 法 简 介 主要内容：算法的表示 算法运行时间 9.2 穷 举 算 法 主要内容：百元百鸡 旅行商问题 9.3 查找算法 主要内容：顺序查找 二分查找 9.4 排 序 算 法 主要内容：直接插入排序 选择排序 冒泡排序 快速排序 CONTENTS 全部章 节
金部章 CONTENTS 9.5 贪婪算法 9.6 动态规划 主要内容：背包问题 主要内容：背包问题 旅行商问题 旅行商问题 9.7 回溯法 9.8 趣味算法 主要内容：八皇后问题 主要内容：兔子产仔问题 谁在说谎 有趣的数字
9.5 贪 婪 算 法 主要内容：背包问题 旅行商问题 9.6 动 态 规 划 主要内容：背包问题 旅行商问题 9.7 回溯法 主要内容：八皇后问题 9.8 趣 味 算 法 主要内容：兔子产仔问题 谁在说谎 有趣的数字 CONTENTS 全部章 节
9.1算法简介 9.1.1引言 算法这个名词听上去很抽象，让人联想不到任何具体的物体。甚至你会觉 得算法与自己的生活并无太多关联，它只是为计算机专业人员或者科学家服务 的。错误的！ 算法无处不在。 食堂买饭：选择一个较短的队列；选择一个推进速度快的队列 每天早上起床，先读一会儿书再去吃早餐；先去吃早餐然后再看书。 所有这些行为都是算法的体现
9.1 算法简介 9.1.1 引言 算法这个名词听上去很抽象，让人联想不到任何具体的物体。甚至你会觉 得算法与自己的生活并无太多关联，它只是为计算机专业人员或者科学家服务 的。错误的！ 算法无处不在。 食堂买饭：选择一个较短的队列； 选择一个推进速度快的队列 每天早上起床，先读一会儿书再去吃早餐；先去吃早餐然后再看书。 所有这些行为都是算法的体现
9.1.2算法是计算机的灵魂 算法：是解决问题的有穷步骤的描述。 排序：比如考试排名，产品评优等。 大家首先想到的排序方法是什么呢？插入法，换一个通俗易懂的说法，就 是人们打牌时整理手中扑克牌的算法。这个算法的效率会随着数据量的增加而 大幅度降低。 每个新的算法都是为了解决前面算法遗留的问题而产生，新算法提高了效 率，同时也会有意或无意的引入新问题，这就是算法永远不会停止发展的一个 原因吧
9.1.2 算法是计算机的灵魂 算法：是解决问题的有穷步骤的描述。 排序：比如考试排名，产品评优等。 大家首先想到的排序方法是什么呢？插入法，换一个通俗易懂的说法，就 是人们打牌时整理手中扑克牌的算法。这个算法的效率会随着数据量的增加而 大幅度降低。 每个新的算法都是为了解决前面算法遗留的问题而产生，新算法提高了效 率，同时也会有意或无意的引入新问题，这就是算法永远不会停止发展的一个 原因吧
9.1.2算法是计算机的灵魂 计算1到100的累加和 方法一：先计算1+2，再将结果加上3，然后再将结果加上4，以此类推，一直 加到100。 方法二：将1+100，然后乘以50即可同样得出答案。 两种方法的时间复杂度不一样，显然第二种方法更快。 由于现代计算机运行速度都非常快，对于运行这样一点小运算来说不会有 明显的时间差异。但是在大型软件项目中，程序的执行效率高低就显得至关重 要，会直接影响到用户体验。因此，合理的算法设计是非常必要的
9.1.2 算法是计算机的灵魂 计算1到100的累加和 方法一：先计算1+2，再将结果加上3，然后再将结果加上4，以此类推，一直 加到 100。 方法二：将 1 + 100，然后乘以50即可同样得出答案。 两种方法的时间复杂度不一样，显然第二种方法更快。 由于现代计算机运行速度都非常快，对于运行这样一点小运算来说不会有 明显的时间差异。但是在大型软件项目中，程序的执行效率高低就显得至关重 要，会直接影响到用户体验。因此，合理的算法设计是非常必要的
9.1.3运行时间 假设在字典中查找一个以M开头的单词，可以从头开始翻页，直到进入以 M开头的部分；还可以从中间开始，因为M开头的单词在字典的中间位置附近。 有100个数字，已经按照从小到大的顺序排列好了。当我们需要找出其中 某一个数字时，可以从头开始比对，最差的情况是需要比对100次；还可以从 中间开始。 对100个数字而言，这种方法最多需要比对7次。如果列表中包含40亿个 数字，最多也只需要比对32次。 二分查找法（折半查找）
9.1.3 运行时间 假设在字典中查找一个以M开头的单词，可以从头开始翻页，直到进入以 M开头的部分；还可以从中间开始，因为M开头的单词在字典的中间位置附近。 有100个数字，已经按照从小到大的顺序排列好了。当我们需要找出其中 某一个数字时，可以从头开始比对，最差的情况是需要比对100次；还可以从 中间开始。 对100个数字而言，这种方法最多需要比对7次。如果列表中包含40亿个 数字，最多也只需要比对32次。 二分查找法（折半查找）
9.1.3运行时间 对长度为n的列表，使用逐个比对的方法就需要执行n次操作， 这个运行时间我们记做O(),也叫线性时间。 如果使用折半的方法仅仅需要执行logn次操作，记做O(Iogn), 也叫对数时间。 不是以秒为单位，仅指出算法运行时间的增速。 O(logn)比O(n)快，当需要搜索的元素越多时，前者比后者快的越多
9.1.3 运行时间 对长度为n的列表，使用逐个比对的方法就需要执行n次操作， 这个运行时间我们记做O(n)，也叫线性时间。 如果使用折半的方法仅仅需要执行log n次操作，记做O(log n)， 也叫对数时间。 不是以秒为单位，仅指出算法运行时间的增速。 O(log n)比O(n)快，当需要搜索的元素越多时，前者比后者快的越多
9.1.4算法的表示 1.自然语言 知道把大象放冰箱一共分几步吗？ 一，把冰箱门打开。 二，把大象塞进去。 三，把冰箱门关上。 这就是用自然语言描述的算法
9.1.4 算法的表示 1.自然语言 知道把大象放冰箱一共分几步吗？ 一，把冰箱门打开。 二，把大象塞进去。 三，把冰箱门关上。 这就是用自然语言描述的算法
9.1.4算法的表示 1.自然语言 古希腊数学家欧几里得（公元前3世纪)曾在他的著作中描述过求两个 数的最大公因子的过程。即两个整数的最大公约数等于其中较小的那个数和两 数相除余数的最大公约数。 算法9.1： (1)输入任意两个整数m和n,使得m>n; m n 12 6 2 (2)计算：m除以n得余数r; 6 2 3 2 3 0 (3)若r=0,则n为求得的最大公约数，算法结束；否则执行(4)； (4)将m的值修改为n,将n的值修改为r,再重复执行(2)
9.1.4 算法的表示 1.自然语言 古希腊数学家欧几里得（公元前3世纪）曾在他的著作中描述过求两个 数的最大公因子的过程。即两个整数的最大公约数等于其中较小的那个数和两 数相除余数的最大公约数。 算法9.1： (1) 输入任意两个整数m和n，使得m>n； (2) 计算：m除以n得余数r； (3) 若r=0，则n为求得的最大公约数，算法结束；否则执行(4)； (4) 将m的值修改为n，将n的值修改为r，再重复执行(2)。 m n r 12 6 2 6 2 3 2 3 0