算法设计与分析 黄刘生 中国科学技术大学计算机系 国家高性能计算中心(合肥) 2008.819
1 算法设计与分析 黄刘生 中国科学技术大学计算机系 国家高性能计算中心（合肥） 2008.8.19
第一部分 概率算法
2 第一部分 概率算法
Ch1绪论 §11引言 1.故事:想象自己是神化故事的主人公,你 有一张不易懂的地图,上面描述了一处宝 藏的藏宝地点。经分析你能确定最有可能 的两个地点是藏宝地点,但二者相距甚远。 假设你如果已到达其中一处,就立即知道 该处是否为藏宝地点。你到达两处之一地 点,以及从其中一处到另一处的距离是5 天的行程。进一步假设有一条恶龙,每晚 光顾宝藏并从中拿走一部分财宝。假设你 取宝藏的方案有两种:
3 Ch.1 绪论 1. 故事：想象自己是神化故事的主人公，你 有一张不易懂的地图，上面描述了一处宝 藏的藏宝地点。经分析你能确定最有可能 的两个地点是藏宝地点，但二者相距甚远。 假设你如果已到达其中一处，就立即知道 该处是否为藏宝地点。你到达两处之一地 点，以及从其中一处到另一处的距离是5 天的行程。进一步假设有一条恶龙，每晚 光顾宝藏并从中拿走一部分财宝。假设你 取宝藏的方案有两种： §1.1 引言 地点 1 地点 2 你 5天 5天 5天
§11引言 方案1.花4天的时间计算出准确的藏宝地点,然 后出发寻宝,一旦出发不能重新计算 方案2.有一个小精灵告诉你地图的秘密,但你 必须付给他报酬,相当于龙3晚上拿走的财宝 Prob1.1.1若忽略可能的冒险和出发寻宝的代 价,你是否接受小精灵的帮助? 显然,应该接受小精灵的帮助,因为你只需 给出3晚上被盗窃的财宝量,否则你将失去4晚被 盗财宝量。 但是,若冒险,你可能做得更好!
4 方案1. 花4天的时间计算出准确的藏宝地点，然 后出发寻宝，一旦出发不能重新计算 方案2. 有一个小精灵告诉你地图的秘密，但你 必须付给他报酬，相当于龙3晚上拿走的财宝 Prob 1.1.1 若忽略可能的冒险和出发寻宝的代 价，你是否接受小精灵的帮助？ 显然，应该接受小精灵的帮助，因为你只需 给出3晚上被盗窃的财宝量，否则你将失去4晚被 盗财宝量。 但是，若冒险，你可能做得更好！ §1.1 引言
§11引言 设x是你决定之前当日的宝藏价值,设y是恶龙每 晚盗走的宝藏价值,并设x>9y 方案1:4天计算确定地址,行程5天,你得到的宝 藏价值为:x-9y 方案2:3y付给精灵,行程5天失去5y,你得到的 宝藏价值为:x-8y 方案3:投硬币决定先到一处,失败后到另一处冒 险方案) 一次成功所得:x5y,机会12 二次成功所得:x-10y,机会12期望赢利:x7,5
5 设x是你决定之前当日的宝藏价值，设y是恶龙每 晚盗走的宝藏价值，并设x>9y 方案1：4天计算确定地址，行程5天，你得到的宝 藏价值为：x-9y 方案2：3y付给精灵，行程5天失去5y，你得到的 宝藏价值为：x-8y 方案3：投硬币决定先到一处，失败后到另一处(冒 险方案) 一次成功所得：x-5y，机会1/2 二次成功所得：x-10y，机会1/2 §1.1 引言 }期望赢利：x-7.5y
2意义 该故事告诉我们:当一个算法面临某种选择 时,有时随机选择比耗时做最优选择更好,尤其 是当最优选择所花的时间大于随机选择的平均时 间的时侯 显然,概率算法只能是期望的时间更有效, 但它有可能遭受到最坏的可能性
6 2. 意义 该故事告诉我们：当一个算法面临某种选择 时，有时随机选择比耗时做最优选择更好，尤其 是当最优选择所花的时间大于随机选择的平均时 间的时侯 显然，概率算法只能是期望的时间更有效， 但它有可能遭受到最坏的可能性
3期望时间和平均时间的区别 令确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时,算法 的平均执行时间。 令概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。 因此,对概率算法可以讨论如下两种期望时间 ①平均的期望时间:所有输入实例上平均的期望执行时 间 ②最坏的期望时间:最坏的输入实例上的期望执行时间
7 3. 期望时间和平均时间的区别 ❖ 确定算法的平均执行时间 输入规模一定的所有输入实例是等概率出现时，算法 的平均执行时间。 ❖ 概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。 因此，对概率算法可以讨论如下两种期望时间 ① 平均的期望时间：所有输入实例上平均的期望执行时 间 ② 最坏的期望时间：最坏的输入实例上的期望执行时间
4.例子 ①快速排序中的随机划分 要求学生写一算法,由老师给出输入实例,按运行时间打分, 大部分学生均不敢用简单的划分,运行时间在1500-2600ms, 个学生用概率的方法划分,运行时间平均为300ms ②8皇后问题 系统的方法放置皇后(回溯法)较合适,找出所有92个解0(2 若只找92个其中的任何一个解可在线性时间内完成On) 随机法:随机地放置若干皇后能够改进回溯法,特别是当n较大 时 ③判断大整数是否为素数 确定算法无法在可行的时间内判断一个数百位十进制数是否素 数,否则密码就不安全。 概率算法将有所作为:若能接受一个任意小的错误的概率
8 4. 例子 ① 快速排序中的随机划分 要求学生写一算法，由老师给出输入实例，按运行时间打分， 大部分学生均不敢用简单的划分，运行时间在1500-2600ms， 三个学生用概率的方法划分，运行时间平均为300ms。 ② 8皇后问题 系统的方法放置皇后(回溯法)较合适，找出所有92个解 O(2 n)， 若只找92个其中的任何一个解可在线性时间内完成O(n)。 随机法：随机地放置若干皇后能够改进回溯法，特别是当n较大 时 ③ 判断大整数是否为素数 确定算法无法在可行的时间内判断一个数百位十进制数是否素 数，否则密码就不安全。 概率算法将有所作为：若能接受一个任意小的错误的概率
5.概率算法的特点 (1)不可再现性 在同一个输入实例上,每次执行结果不尽相同,例 如 ①N-皇后问题 概率算法运行不同次将会找到不同的正确解 ②找一给定合数的非平凡因子 每次运行的结果不尽相同,但确定算法每次运行结果必 定相同 (2)分析困难 要求有概率论,统计学和数论的知识 9
9 5. 概率算法的特点 (1) 不可再现性 在同一个输入实例上，每次执行结果不尽相同，例 如 ① N-皇后问题 概率算法运行不同次将会找到不同的正确解 ② 找一给定合数的非平凡因子 每次运行的结果不尽相同，但确定算法每次运行结果必 定相同 (2) 分析困难 要求有概率论，统计学和数论的知识
6.约定 随机函数 uniform:随机,均匀,独立 ①设a,b为实数,a<b, uniform(a,b)返回x,a≤x<b ②设,j为整数,图, uniform(,)=k,isk≤j ③设X是非空有限集, uniforn(x)∈X 10
10 6. 约定 随机函数uniform：随机，均匀，独立 ① 设a，b为实数，a<b, uniform(a, b) 返回x，a ≤ x <b ② 设i，j为整数，i≤j, uniform(i..j)=k, i ≤ k ≤ j ③ 设X是非空有限集， uniform(X) ∈ X