隐藏信息检测与还原技术-中国科学技术大学优秀PPT.ppt

《隐藏信息检测与还原技术-中国科学技术大学优秀PPT.ppt》由会员分享，可在线阅读，更多相关《隐藏信息检测与还原技术-中国科学技术大学优秀PPT.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析黄刘生黄刘生中国科学技术高校中国科学技术高校计算机系计算机系 国家高性能计算国家高性能计算中心（合肥）中心（合肥）1第一部分第一部分概率算法概率算法2Ch.1 绪论绪论1.故故事事：想想象象自自己己是是神神化化故故事事的的主主子子公公，你你有有一一张张不不易易懂懂的的地地图图，上上面面描描述述了了一一处处宝宝藏藏的的藏藏宝宝地地点点。经经分分析析你你能能确确定定最最有有可可能能的的两两个个地地点点是是藏藏宝宝地地点点，但但二二者者相相距距甚甚远远。假假设设你你假假如如已已到到达达其其中中一一处处，就就马马上上知知道道该该处处是是否否为为藏藏宝宝地地点点。你你到到达达

2、两两处处之之一一地地点点及及从从其其中中一一处处到到另另一一处处的的距距离离是是5天天的的行行程程。进进一一步步假假设设有有一一条条恶恶龙龙，每每晚晚光光顾顾宝宝藏藏并并从从中中拿拿走走一一部部分分财财宝宝。假假设设你你取取宝宝藏的方案有两种：藏的方案有两种：1.1 引言引言3 方方案案1.花花4天天的的时时间间计计算算出出精精确确的的藏藏宝宝地地点点，然然后动身寻宝，一旦动身不能重新计算后动身寻宝，一旦动身不能重新计算 方方案案2.有有一一个个小小精精灵灵告告知知你你地地图图的的隐隐私私，但但你你必需付给他酬劳，相当于龙必需付给他酬劳，相当于龙3晚上拿走的财宝晚上拿走的财宝 Prob 1.1

3、.1 若若忽忽视视可可能能的的冒冒险险和和动动身身寻寻宝宝的的代代价价，你是否接受小精灵的帮助？你是否接受小精灵的帮助？明明显显，应应当当接接受受小小精精灵灵的的帮帮助助，因因为为你你只只需需给给出出3晚晚上上被被盗盗窃窃的的财财宝宝量量，否否则则你你将将失失去去4晚晚被被盗财宝量。盗财宝量。但是，若冒险，你可能做得更好！但是，若冒险，你可能做得更好！1.1 引言引言4 设设x是是你你确确定定之之前前当当日日的的宝宝藏藏价价值值，设设y是是恶恶龙龙每每晚盗走的宝藏价值，并设晚盗走的宝藏价值，并设x9y 方方案案1：4天天计计算算确确定定地地址址，行行程程5天天，你你得得到到的的宝宝藏价值为：藏

4、价值为：x-9y 方方案案2：3y付付给给精精灵灵，行行程程5天天失失去去5y，你你得得到到的的宝藏价值为：宝藏价值为：x-8y 方方案案3：投投硬硬币币确确定定先先到到一一处处，失失败败后后到到另另一一处处(冒险方案冒险方案)一次成功所得：一次成功所得：x-5y，机会，机会1/2 二次成功所得：二次成功所得：x-10y，机会，机会1/21.1 引言引言期望赢利：期望赢利：x-7.5y52.意义意义 该故事告知我们：当一个算法面临某种选择该故事告知我们：当一个算法面临某种选择时，有时随机选择比耗时做最优选择更好，尤其时，有时随机选择比耗时做最优选择更好，尤其是当最优选择所花的时间大于随机选择的

5、平均时是当最优选择所花的时间大于随机选择的平均时间的时侯间的时侯 明显，概率算法只能是期望的时间更有效，明显，概率算法只能是期望的时间更有效，但它有可能遭遇到最坏的可能性。但它有可能遭遇到最坏的可能性。63.期望时间和平均时间的区分期望时间和平均时间的区分确定算法的平均执行时间确定算法的平均执行时间 输入规模确定的全部输入实例是等概率出现时，输入规模确定的全部输入实例是等概率出现时，算法的平均执行时间。算法的平均执行时间。概率算法的期望执行时间概率算法的期望执行时间 反复解同一个输入实例所花的平均执行时间。反复解同一个输入实例所花的平均执行时间。因此，对概率算法可以探讨如下两种期望时间因此，对

6、概率算法可以探讨如下两种期望时间平均的期望时间：全部输入实例上平均的期望执行平均的期望时间：全部输入实例上平均的期望执行时间时间最坏的期望时间：最坏的输入实例上的期望执行时最坏的期望时间：最坏的输入实例上的期望执行时间间74.例子例子快速排序中的随机划分快速排序中的随机划分要求学生写一算法，由老师给出输入实例，按运行时间打分，要求学生写一算法，由老师给出输入实例，按运行时间打分，大部分学生均不敢用简洁的划分，运行时间在大部分学生均不敢用简洁的划分，运行时间在1500-2600ms，三个学生用概率的方法划分，运行时间平均为，三个学生用概率的方法划分，运行时间平均为300ms。8皇后问题皇后问题系

7、统的方法放置皇后系统的方法放置皇后(回溯法回溯法)较合适，找出全部较合适，找出全部92个解个解 O(2n)，若只找，若只找92个其中的任何一个解可在线性时间内完成个其中的任何一个解可在线性时间内完成O(n)。随机法：随机地放置若干皇后能够改进回溯法，特殊是当随机法：随机地放置若干皇后能够改进回溯法，特殊是当n较大时较大时推断大整数是否为素数推断大整数是否为素数确定算法无法在可行的时间内推断一个数百位十进制数是否确定算法无法在可行的时间内推断一个数百位十进制数是否素数，否则密码就担忧全。素数，否则密码就担忧全。概率算法将有所作为：若能接受一个随意小的错误的概率概率算法将有所作为：若能接受一个随意

8、小的错误的概率85.概率算法的特点概率算法的特点 (1)不行再现性不行再现性 在同一个输入实例上，每次执行结果不尽相同，例在同一个输入实例上，每次执行结果不尽相同，例如如N-皇后问题皇后问题概率算法运行不同次将会找到不同的正确解概率算法运行不同次将会找到不同的正确解找一给定合数的非平凡因子找一给定合数的非平凡因子每次运行的结果不尽相同，但确定算法每次运行结每次运行的结果不尽相同，但确定算法每次运行结果必定相同果必定相同 (2)分析困难分析困难 要求有概率论，统计学和数论的学问要求有概率论，统计学和数论的学问96.约定约定 随机函数随机函数uniform：随机，匀整，独立：随机，匀整，独立设设a

9、，b为实数，为实数，ab,uniform(a,b)返回返回x，a x b 设设i，j为整数，为整数，ij,uniform(i,j)=k,i k j 设设X是非空有限集，是非空有限集，uniform(X)X 10例例1：设p是是一一个个素素数数，a是是一一个个整整数数满足足1a0 do if(j is odd)s sa mod p;a a2 mod p;j j div 2;return s;Draw(a,p)/在在X中随机取一元素中随机取一元素j uniform(1.p-1);return ModularExponent(a,j,p);/在在X中随机取一元素中随机取一元素12n伪随机数发生器伪随

10、机数发生器n在好用中不行能有真正的随机数发生器，多数状在好用中不行能有真正的随机数发生器，多数状况下是用伪随机数发生器代替。况下是用伪随机数发生器代替。n大多数伪随机数发生器是基于一对函数：大多数伪随机数发生器是基于一对函数：nS:X X,S:X X,这里这里X X足够大，它是种子的值足够大，它是种子的值域域nR:X Y,YR:X Y,Y是伪随机数函数的值域是伪随机数函数的值域n运用运用S S获得种子序列：获得种子序列：x0=g,xi=S(xi-1),i0 x0=g,xi=S(xi-1),i0n然后运用然后运用R R获得伪随机序列：获得伪随机序列：yi=R(xi),i 0yi=R(xi),i

11、0n该序列必定是周期性的，但只要该序列必定是周期性的，但只要S S和和R R选的合适，选的合适，该周期长度会特别长。该周期长度会特别长。nTCTC中可用中可用rand()rand()和和srand(time),srand(time),用用GNU CGNU C更好更好131.基本特征基本特征2.随机决策随机决策3.在同一实例上执行两次其结果可能不同在同一实例上执行两次其结果可能不同4.在同一实例上执行两次的时间亦可能不太相在同一实例上执行两次的时间亦可能不太相同同5.分类分类6.Numerical,Monte Carlo,Las Vegas,Sherwood.7.很多人将全部概率算法很多人将全部

12、概率算法(尤其是数字的概率算尤其是数字的概率算法法)称为称为Monte Carlo算法算法1.2 概率算法的分类概率算法的分类14数字算法数字算法随机性被最早用于求数字问题的近似解随机性被最早用于求数字问题的近似解例如，求一个系统中队列的平均长度的问题，确定例如，求一个系统中队列的平均长度的问题，确定算法很难得到答案算法很难得到答案概率算法获得的答案一般是近似的，但通常算法执行的时概率算法获得的答案一般是近似的，但通常算法执行的时间越长，精度就越高，误差就越小间越长，精度就越高，误差就越小运用的理由运用的理由现实世界中的问题在原理上可能就不存在精确解现实世界中的问题在原理上可能就不存在精确解例

13、如，试验数据本身就是近似的，一个无理数在计例如，试验数据本身就是近似的，一个无理数在计算机中只能近似地表示算机中只能近似地表示精确解存在但无法在可行的时间内求得精确解存在但无法在可行的时间内求得有时答案是以置信区间的形式给出的有时答案是以置信区间的形式给出的1.2 概率算法的分类概率算法的分类15Monte Carlo算法算法(MC算法算法)蒙特卡洛算法蒙特卡洛算法1945年由年由J.Von Neumann进行核武模拟进行核武模拟提出的。它是以概率和统计的理论与方法为基础的一种数值计提出的。它是以概率和统计的理论与方法为基础的一种数值计算方法，它是双重近似：一是用概率模型模拟近似的数值计算，算

14、方法，它是双重近似：一是用概率模型模拟近似的数值计算，二是用伪随机数模拟真正的随机变量的样本。二是用伪随机数模拟真正的随机变量的样本。这里我们指的这里我们指的MC算法是：算法是：若问题只有若问题只有1个正确的解，个正确的解，而无近似解的可能时运用而无近似解的可能时运用MC算法算法例如，判定问题只有真或假两种可能性，没有近似解例如，判定问题只有真或假两种可能性，没有近似解 因式分解，我们不能说某数几乎是一个因子因式分解，我们不能说某数几乎是一个因子特点：特点：MC算法总是给出一个答案，但该答案未必正确，成功算法总是给出一个答案，但该答案未必正确，成功(即答案是正确的即答案是正确的)的概率正比于算

15、法执行的时间的概率正比于算法执行的时间缺点：一般不能有效地确定算法的答案是否正确缺点：一般不能有效地确定算法的答案是否正确1.2 概率算法的分类概率算法的分类16Las Vegas算法算法(LV算法算法)LV算法绝不返回错误的答案。算法绝不返回错误的答案。特点：获得的答案必定正确，但有时它仍根本就找不到特点：获得的答案必定正确，但有时它仍根本就找不到答案。答案。和和MC算法一样，成功的概率亦随算法执行时间增加算法一样，成功的概率亦随算法执行时间增加而增加。无论输入何种实例，只要算法在该实例上运行而增加。无论输入何种实例，只要算法在该实例上运行足够的次数，则算法失败的概率就随意小。足够的次数，则

16、算法失败的概率就随意小。Sherwood算法算法Sherwood算法总是给出正确的答案。算法总是给出正确的答案。当某些确定算法解决一个特殊问题平均的时间比当某些确定算法解决一个特殊问题平均的时间比最坏时间快得多时，我们可以运用最坏时间快得多时，我们可以运用Sherwood算法来削算法来削减，甚至是消退好的和坏的实例之间的差别。减，甚至是消退好的和坏的实例之间的差别。1.2 概率算法的分类概率算法的分类17这类算法主要用于找到一个数字问题的近似解这类算法主要用于找到一个数字问题的近似解2.1 值计算值计算试验：将试验：将n根飞镖随机投向一正方形的靶子，计算落入此正方形的根飞镖随机投向一正方形的靶

17、子，计算落入此正方形的内切圆中的飞镖数目内切圆中的飞镖数目k。假定飞镖击中方形靶子任一点的概率相等假定飞镖击中方形靶子任一点的概率相等(用计算机模拟比任用计算机模拟比任一飞镖高手更能保证此假设成立一飞镖高手更能保证此假设成立)设圆的半径为设圆的半径为r，面积，面积s1=r2；方靶面积方靶面积s2=4r2由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由等概率假设可知落入圆中的飞镖和正方形内的飞镖平均比为：由此知：由此知：Ch.2 数字概率算法数字概率算法181.求求近似值的算法近似值的算法2.为简洁起见，只以上图的右上为简洁起见，只以上图的右上1/4象限为样本象限为样本3.Darts(

18、n)4.k 0;5.for i 1 to n do 6.x uniform(0,1);7.y uniform(0,1);/随机产生点随机产生点(x,y)8.if(x2+y2 1)then k+;/圆内圆内9.10.return 4k/n;11.12.试验结果：试验结果：=3.14159265413.n=1000万万:3.140740,3.142568(2位精确位精确)14.n=1亿亿:3.141691,3.141363(3位精确位精确)15.n=10亿亿:3.141527,3.141507(4位精确位精确)2.1 值计算值计算191.求求近似值的算法近似值的算法2.Ex.1 若将若将y uni

19、form(0,1)改为改为 y x,则则上述的算法估计的值是什么？上述的算法估计的值是什么？2.1 值计算值计算20Monte Carlo积分积分(但不是指我们定义的但不是指我们定义的MC算法算法)概率算法概率算法1设设f:0,1 0,1是一个连续函数，则由曲线是一个连续函数，则由曲线y=f(x),x轴轴,y轴和直线轴和直线x=1围成的面积由下述积分给出：围成的面积由下述积分给出：向单位面积的正方形内投镖向单位面积的正方形内投镖n次，落入阴影部分的镖的次，落入阴影部分的镖的数目为数目为k，则，则 明显，只要明显，只要n足够大足够大 2.2 数字数字积分分(计算定算定积分的分的值)211.概率算

20、法概率算法12.HitorMiss(f,n)3.k 0;4.for i 1 to n do 5.x uniform(0,1);6.y uniform(0,1);7.if y f(x)then k+;8.9.return k/n;10.Note:是是S/4的面积，的面积，=S,2.2 数字数字积分分(计算定算定积分的分的值)221.概率算法概率算法12.Ex2.在机器上用在机器上用 估计估计值，给出值，给出不同的不同的n值及精度。值及精度。3.Ex3.设设a,b,c和和d是实数，且是实数，且a b,c d,f:a,b c,d是一个连续函数，写一概率算是一个连续函数，写一概率算法计算积分：法计算积

21、分：4.5.留意，函数的参数是留意，函数的参数是a,b,c,d,n和和f,其中其中f用用函数指针实现，请选一连续函数做试验，并给函数指针实现，请选一连续函数做试验，并给出试验结果。出试验结果。2.2 数字数字积分分(计算定算定积分的分的值)231.概率算法概率算法12.*Ex4.设设,是是(0,1)之间的常数，证明：之间的常数，证明：3.若若I是是 的正确值，的正确值，h是由是由HitorHiss算法返回的值，算法返回的值，则当则当n I(1-I)/2时有：时有：4.Prob|h-I|1 5.上述的意义告知我们：上述的意义告知我们：Prob|h-I|,即：当即：当n I(1-I)/2时，算法的

22、计算结果的确定误差超过时，算法的计算结果的确定误差超过的概率的概率不超过不超过，因此我们依据给定，因此我们依据给定和和可以确定算法迭代的可以确定算法迭代的次数次数6.7.8.解此问题时可用切比雪夫不等式，将解此问题时可用切比雪夫不等式，将I看作是数学期看作是数学期望。望。2.2 数字数字积分分(计算定算定积分的分的值)242.概率算法概率算法23.更有效的概率算法是：更有效的概率算法是：在积分区间上随机匀整地产生在积分区间上随机匀整地产生点，求出这些点上的函数值的算术平均值，再乘以区间的宽度：点，求出这些点上的函数值的算术平均值，再乘以区间的宽度：4.Crude(f,n,a,b)5.sum 0

23、;6.for i 1 to n do 7.x uniform(a,b);8.sum sum+f(x);9.10.return(b-a)sum/n;11.2.2 数字数字积分分(计算定算定积分的分的值)252.概率算法概率算法2用用HitorMiss和和Crude运行三次的结果为：运行三次的结果为：假假定定 和和 存存在在，由由算算法法求求得得的的估估算算值值的的方方差差反反比比于于点点数数n。当当n足足够够大大时时，估估计计的的分分布近似为正态分布。布近似为正态分布。对对于于给给定定的的迭迭代代次次数数n，Crude算算法法的的方方差差不不会会大大于于HitorMiss的的方方差差。但但不不能

24、能说说，Crude算算法法总总是是优优于于HitorMiss。因因为为后后者者在在给给定定的的时时间间内内能能迭迭代代的的次次数数更更多多。例例如如，计计算算值时，Crude需需计算算平平方根，而用投方根，而用投镖算法算法darts时无需无需计算平方根。算平方根。2.2 数字数字积分分(计算定算定积分的分的值)263.确定的算法确定的算法梯形算法梯形算法将区间分为将区间分为n-1个子区间，每个子区间内的长度为个子区间，每个子区间内的长度为，Trapezoid(f,n,a,b)/假设假设 n 2delta (b-a)/(n-1);sum (f(a)+f(b)/2;for x a+delta st

25、ep delta to b delta dosum sum+f(x)return sum delta;2.2 数字数字积分分(计算定算定积分的分的值)273.确定的算法确定的算法 1.当当n=100,=3.1403992.当当n=1,000,=3.141555 当当n=10,000,=3.141586 当当n=100,000,=3.141593一一般般地地，在在同同样样的的精精度度下下，梯梯形形算算法法的的迭迭代代次次数数少少于于MC积积分，但是分，但是有有时确定型确定型积分算法求不出解：分算法求不出解：例如，例如，f(x)=sin2(100)!x)，。但但是是用用梯梯形形算算法法时，当当2

26、n101时时，返返回回值值是是0。若若用用MC积分分则不不会会发生生该类问题，或或虽然然发生生，但但概概率率小小得多。得多。2.2 数字数字积分分(计算定算定积分的分的值)28多重积分多重积分 在在确确定定算算法法中中，为为了了达达到到确确定定的的精精度度，采采样样点点的的数数目目随随着着积积分分维维数数成成指指数数增增长长，例例如如，一一维维积积分分若若有有100个个点点可可达达到到确确定定的的精精度度，则则二二维维积积分分可可能能要要计计算算1002个个点点才才能能达达到到同同样样的的精精度度，三三维维积积分分则则需需计计算算1003个点。个点。(系统的方法系统的方法)但但概概率率算算法法

27、对对维维数数的的敏敏感感度度不不大大，仅仅是是每每次次迭迭代代中中计计算算的的量量稍稍增增一一点点，事事实实上上，MC积积分分特特殊殊适合用于计算适合用于计算4或更高维数的定积分。或更高维数的定积分。若若要要提提高高精精度度，则则可可用用混混合合技技术术：部部分分接接受受系统的方法，部分接受概率的方法系统的方法，部分接受概率的方法2.2 数字数字积分分(计算定算定积分的分的值)29 上上一一节节可可以以认认为为，数数字字概概率率算算法法被被用用来来近近似似一一个个实实数数，本本节节可可用用它它们们来来估估计计一一个个整整数数值值。例例如如，设设X为为有有限限集集，若若要要求求X的的势势|X|，

28、则则当当X较较大大时，枚举明显不现实。时，枚举明显不现实。问问题题：随随机机选选出出25人人，你你是是否否情情愿愿赌赌其其中中至至少少有有两两个个人人生生日日相相同同吗吗？直直觉觉告告知知我我们们，一一般般人人都都不不情情愿愿赌其成立，但事实上成立的概率大于赌其成立，但事实上成立的概率大于50%。2.3 概率概率计数数30 一般地，从一般地，从n个对象中选出个对象中选出k个互不相同的对象，若考虑个互不相同的对象，若考虑 选择的次序，则不同的选择有选择的次序，则不同的选择有 种；若允许重复选取同种；若允许重复选取同 一对象，则不同的选法共有一对象，则不同的选法共有 种。种。因因此此，从从n个个对

29、对象象(允允许许同同一一对对象象重重复复取取多多次次)中中随随机机匀匀整整地地选选择择出出的的k个个对对象象互互不不相相同同的的概概率率是是：，留留意意a，b和和b，a是是不不同同的的取取法法。由由此此可可知知，上上述述问问题题中中，25个个人人生日互不相同的概率是：生日互不相同的概率是：这里假设：不考虑润年，一年中人的生日是匀整分布的。这里假设：不考虑润年，一年中人的生日是匀整分布的。2.3 概率概率计数数31由由Stirling公式知：公式知：可得可得 假定假定 Tj;3.2 随机的随机的预处理理51例例2：离散对数计算：离散对数计算离散对数计算困难使其可用于密码算法，数字签名等离散对数计

30、算困难使其可用于密码算法，数字签名等定义：设定义：设 a=gx mod p，记记 logg,pa=x，称，称x为为a的的(以以g为底模为底模除除p)对数对数从从p，g，a计算计算x称为离散对数问题。称为离散对数问题。简洁算法：简洁算法：计算计算gx对全部的对全部的x，最多计算，最多计算0 x p-1 或或 1xp，因为事，因为事实上离散对数实上离散对数是循环群；是循环群；验证验证a=gx mod p 是否成立。是否成立。dlog(g,a,p)/当这样的对数不存在时，算法返回当这样的对数不存在时，算法返回p x 0;y 1;do x+;y y*g;/计算计算y=gx while(a y mod

31、p)and(x p);return x3.2 随机的随机的预处理理52问题：最坏问题：最坏O(p)循环次数难以预料，当满足确定条件时平均循环循环次数难以预料，当满足确定条件时平均循环p/2次次当当p=24位十进制数，循环位十进制数，循环1024次，千万亿次次，千万亿次/秒秒(1016次次/秒秒)大约算大约算1年年(108秒秒/年年)若若p是数百位十进制？随机选择都可能无法在可行的时间内是数百位十进制？随机选择都可能无法在可行的时间内求解。求解。假设有一个平均时间性能很好，但最坏状况差的确定算法求假设有一个平均时间性能很好，但最坏状况差的确定算法求logp,ga，怎样用，怎样用Sherwood算

32、法求解该问题？算法求解该问题？设设p=19,g=2当当a=14,6时，时，log2,1914=7,log2,196=14，即用，即用dlog求求14和和6的离散对数时，分别要循环的离散对数时，分别要循环7和和14次，执行时间与次，执行时间与a的取值相关。的取值相关。用用sherwood算法应当使得与算法应当使得与a无关，用随机预处理的方法计算无关，用随机预处理的方法计算logg,pa3.2 随机的随机的预处理理53定理定理(见见p877,31.6)dlogRH(g,a p)/求求logg,pa,a=gx mod p，求求x /Sherwood算法算法 r uniform(0.p-2);b Mo

33、dularExponent(g,r,p);/求幂模求幂模b=gr mod p c ba mod p;/(gr modp)(gxmodp)modp=gr+xmodp=c y logg,pc;/运用确定性算法求运用确定性算法求logp,gc,y=r+x return(y-r)mod(p-1);/求求xEx.分析分析dlogRH的工作原理，指出该算法相应的的工作原理，指出该算法相应的u和和v3.2 随机的随机的预处理理54随机预处理供应了一种加密计算的可能性随机预处理供应了一种加密计算的可能性 假定你想计算某个实例假定你想计算某个实例x，通过，通过f(x)计算，但你计算，但你缺乏计算实力或是缺乏有效

34、算法，而别人有相应的计算缺乏计算实力或是缺乏有效算法，而别人有相应的计算实力，情愿为你计算实力，情愿为你计算(可能会收费可能会收费)，若你情愿别人帮你，若你情愿别人帮你计算，但你不情愿泄露你的输入实例计算，但你不情愿泄露你的输入实例x，你将如何做？，你将如何做？可将随机预处理运用到可将随机预处理运用到f的计算上：的计算上：运用函数运用函数u将将x加密为某一随机实例加密为某一随机实例y 将将y提交给提交给f计算出计算出f(y)的值的值 运用函数运用函数v转换为转换为f(x)上述过程，他人除了知道你的实例大小外，上述过程，他人除了知道你的实例大小外，不知道不知道x的任何信息，因为的任何信息，因为u

35、(x,r)的概率分布的概率分布(只要只要r是随是随机匀整选择的机匀整选择的)是独立于是独立于x的。的。3.2 随机的随机的预处理理55 设两个数组设两个数组val1.n和和ptr1.n及及head构成一构成一个有序的静态链表：个有序的静态链表：valhead valptrhead valptrptrhead valptrn-1head例：例：3.3 搜搜寻寻有序表有序表 i 1 2 3 4 5 6 7vali 2 3 13 1 5 21 8ptri 2 5 6 1 7 0 3rank 2 3 6 1 4 7 5head=4 有序表：有序表：1，2，3，5，8，13，21 56n折折半半查查找找

36、：若若val1.n本本身身有有序序，可可用用折折半半查查找找找找某某个个给给定定的的key，时间为，时间为O(lgn)。n依依次次查查找找：但但此此表表为为链链式式结结构构，故故最最坏坏时时间间是是(n)。尽尽管管如如此此，我们能够找到一个确定性算法，平均时间为我们能够找到一个确定性算法，平均时间为 。n 相相应应的的Sherwood算算法法的的期期望望时时间间是是 ，它它虽虽然然并并不不比比确定性算法快，但他消退了最坏实例。确定性算法快，但他消退了最坏实例。n 假假定定表表中中元元素素互互不不相相同同，且且所所求求的的关关键键字字在在表表中中存存在在，则给定则给定x，我们是求下标，我们是求下

37、标i，使，使vali=x,这里这里1i n。n任何实例可以由两个参数刻画：任何实例可以由两个参数刻画：n 前前n个整数的排列个整数的排列n x的的rank3.3 搜搜寻寻有序表有序表57设设Sn是全部是全部n!个排列的集合，设个排列的集合，设A是一个确定性算法是一个确定性算法 tA(n,k,)表表示示算算法法A的的执执行行时时间间，此此时时间间与与被被查查找找元元素素的的秩秩k，以以及及val的的排排列列相相关关。若若A是是一一个个概概率率算算法法，则则tA(n,k,)表表示示算算法法的的期期望望值值。无无论论算算法法是是确确定定的的还还是是概概率率的的，wA(n)和和mA(n)分分别别表表示

38、示最最坏坏时间和平均时间，因此有：时间和平均时间，因此有：3.3 搜搜寻寻有序表有序表581.时间为时间为O(n)的确定算法的确定算法2.算法算法3.设设xvali且且x在表中，则从位置在表中，则从位置i起先查找起先查找x的算法为：的算法为：4.Search(x,i)/仍可改进仍可改进5.while x vali do6.i ptri;7.return i;8.9.在表在表val1.n中查找中查找x的算法为：的算法为：10.A(x)11.return Search(x,head);12.3.3 搜搜寻寻有序表有序表59n性能分析性能分析n设设rank(x)=k,则：则：n 算法算法A在在n个元

39、素的表中查找个元素的表中查找x所需所需的访问数组元素的次数，明显与的访问数组元素的次数，明显与无关无关n 算法算法A最坏时的访问次数最坏时的访问次数n 算法算法A平均的访问次数平均的访问次数n nnn 3.3 搜搜寻寻有序表有序表602.时间为时间为O(n)的概率算法的概率算法n算法算法 D(x)i uniform(1.n);y vali;case x y:return Search(x,ptri);/case2 otherwise:return i;/case3，x=y 3.3 搜搜寻寻有序表有序表61n性能分析性能分析(D访问数组次数访问数组次数)n 一般状况一般状况n 设设rank(x)

40、=k,rank(vali)=j n若若 k j,则则 ，属于，属于case2，从，从jth最小元之后搜最小元之后搜寻寻n若若 k=j,则则 ，属于，属于case3n 最坏状况最坏状况n n n3.3 搜搜寻寻有序表有序表62 平均状况平均状况 3.3 搜搜寻寻有序表有序表633.平均时间为平均时间为 的确定算法的确定算法4.算法算法5.B(x)/设设x在在val1.n中中6.i head;7.max vali;/max初值是表初值是表val中最小值中最小值8.for j 1 to do /在在val的前的前 个数中找不大个数中找不大于于x 9.y valj;/的最大整数的最大整数y相应的下标相

41、应的下标i10.if max y x then 11.i j;12.max y;13./endif14./endfor15.return Search(x,i);/从从y起先接着搜寻起先接着搜寻16.3.3 搜搜寻寻有序表有序表64n性能分析性能分析n for循环的目的：找不超过循环的目的：找不超过x的最大整数的最大整数y，使搜寻从，使搜寻从y起先，若将起先，若将val1.n中的中的n个整数看作是匀整随机分布的，个整数看作是匀整随机分布的，则在则在val1.L中求中求y值就相当于在值就相当于在n个整数中，随机地取个整数中，随机地取L个个整数，求这整数，求这L个整数中不大于个整数中不大于x的最大

42、整数的最大整数y。n 可用一个与可用一个与L和和n相关的随机变量来分析，更简洁的相关的随机变量来分析，更简洁的分析如下：分析如下：n设设n个整数的排列满足：个整数的排列满足：a1 a2 ann将其等分为将其等分为L个区间：个区间：n 3.3 搜搜寻寻有序表有序表65 若若匀匀整整随随机机地地从从上上述述表表中中取取L个个数数，则则平平均均每每个个区区间间中中被被选选到到1个个元元素素（留留意意：因因为为val的的随随机机匀匀整整性性，这这里里所所取取的的L个个数数相相当当于于val1.L中中的的L个个数数），因因此此无无论论x是是处处在在哪哪一一个个区区间间，其其平平均均的的执执行行时时间间为

43、：为：i)若若在在x的的同同一一区区间间中中取取到到的的数数小小于于等等于于x，则则它它是是算算法法中中的的y，那那么么Search的的比比较较次次数数不不超超过过区区间间长度长度n/l。ii)若若在在x的的同同一一区区间间中中取取到到的的数数大大于于x，则则在在x的的前前一一区区间间中中的的取取到到的的数数必必为为算算法法中中的的y，它它必必定定小小于于x，且且x和和y的的距距离离平平均均为为n/l，此此时时Search的的比比较较次数平均为次数平均为n/l。3.3 搜搜寻寻有序表有序表66留意，在留意，在Search前需执行前需执行L次循环，故有次循环，故有 因此，确定性算法中因此，确定性算法中for的次数为的次数为 ，此时算法的，此时算法的平均时间平均时间 最小。最小。Ex.写一写一Sherwood算法算法C，与算法，与算法A,B,D比较，比较，给出试验结果。给出试验结果。3.3 搜搜寻寻有序表有序表67