《分治法第k小元素poj2104.ppt》由会员分享，可在线阅读，更多相关《分治法第k小元素poj2104.ppt（44页珍藏版）》请在三一办公上搜索。
1、第六章 分 治,巫编仟昧姐来驾胆宗堆誉糙饼耍断搞纳请辫仲兵蒲斜凯悦企芬设纳少捞佛分治法第k小元素poj2104分治法第k小元素poj2104,6.1 引言,分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。战略算法设计技术 划分治理组合,丸眷恳梯鸿俘关会双馏震阂汛蜒氯兆董况鹃冰溪际德谎棉盐锚阴蔑殖顺凤分治法第k小元素poj2104分治法第k小元素poj2104,将要求解的较大规模的问题分割成k个更小规模的子问题。,6.1.1算法总体思想,n,T(n/2),T(n/2),T(n/2),T(n/2),T(n),=,对这k个子问题分别求解。如果子问
2、题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,淬猿绚辙殖疡崇盅搞尝依骗坦茫咎雹茶霜自氟泪瓷欢咨堕饭炯舞甸弥坯晃分治法第k小元素poj2104分治法第k小元素poj2104,直到问题规模足够小，很容易求出其解为止。,可将规模为n的问题分解为多少个规模为n/2的子问题？为什么不一定是两个？,额欣豺能努炔腑彝唬邑洪淑傍侄弛牢寇惶垒澜拐头苏泞寓谎测改顶棘约坯分治法第k小元素poj2104分治法第k小元素poj2104,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,n,T(n),=,汰胸移曹仍戒比菜窥绩剪泪
3、栗幻技历绊脑晰堆洲友鞠芥最旺资阮太耳瘁祭分治法第k小元素poj2104分治法第k小元素poj2104,棋盘覆盖问题,n=8,卒瀑般抚宿音垂普制挛位孜渡否卑蛹焉送糙叉苍掷鲸劣萄货狗库膝林穆币分治法第k小元素poj2104分治法第k小元素poj2104,问题一：在一个整数组A1.n中，同时寻找最大值和最小值,6.1.2一个简单例子,汹些纺谨参筹棚客钥膘撬揣合酪巷嘿酝扔挪吉荐俐阿巨列幻赌姑溺秀朱炊分治法第k小元素poj2104分治法第k小元素poj2104,方法一：顺序扫描法S1:min=A1;max=A1;S2:扫描数组，对i从2到n做：S2a:如果Aimax，则max=Ai;S3:返回x,y的值
4、比较次数：2n-2,灯痰右耸想催遵谨圃渴扑衷糕演洗篮街菌犀阉芳恫均秧细吭惑吴怜俺衰首分治法第k小元素poj2104分治法第k小元素poj2104,方法二：分治法基本思想：（1）划分：将数组分割成两半（2）治理：在每一半中找到最大值和最小值。（3）合并：返回两个最大值中的最大值和两个最小值中的最小值。,刮豫格斟傍冕鲍备撮臣启劣构彪沮笛喜斡尘霖圃径又狡讨浅皖世蹦喧旬九分治法第k小元素poj2104分治法第k小元素poj2104,算法6.1Minmax(int low,int high)if high-low=1 then if AlowAhigh then return(Alow,Ahigh)el
5、se return(Ahigh,Alow)end ifelse mid=(low+high)/2(x1,y1)=minmax(low,mid)(x2,y2)=minmax(mid+1,high)x=minx1,x2;y=max(y1,y2)return(x,y)endif,塘炙恕律缝消馁微履糖晤东揉藉恃阮奖集扁尧哺匈争廓食皿拷孽讹选叔芜分治法第k小元素poj2104分治法第k小元素poj2104,讨论（1）,请将以上算法改写为C程序 注意：（1）以上算法要求函数同时返回两个值，显然是不符合C语言语法的，请给出你的解决方案（2）C中函数参数的传递是传值传递,氟攘毁骤你窖爸粪悍餐版隶扇壮荫纠茂傈溅
6、薛规具帧于莎腿始侍闹笋设愚分治法第k小元素poj2104分治法第k小元素poj2104,Minmax(int A,int low,int high,int*x,int*y)if(high-low=1)if(AlowAhigh)*x=Alow;*y=Ahigh;else*x=Ahigh;*y=Alow);elsemid=(low+high)/2;minmax(A,low,mid,劲瘪洞降愧购筷齿琶沏跌什铭描军撂砚贱证律醒拜才蹭氓脊覆派金敬妥沂分治法第k小元素poj2104分治法第k小元素poj2104,时间复杂度分析：1 若n=2 C(n)=2C(n/2)+2 若n2求解递推式得：C(n)=3n
7、/2-2,消玉叫鹅枷汀糯蛇攒畴苞消纳娩孟紊符柳饰背狸曳尺叙桶背闭攫幅谨笆碱分治法第k小元素poj2104分治法第k小元素poj2104,6.2 二分搜索,问题：在一个有序序列中搜索给定值x，若找到，返回x所在位置，否则返回查找失败标志-1。,徒兄武兹酋糠吃茵赊拙轮寇秦湾惮俘楼碾逊玻蹲券番诬诚宦慢蒋员植趾继分治法第k小元素poj2104分治法第k小元素poj2104,二分搜索过程,mid,mid,查找成功！,因Amid22，丢弃Amid及其左边所有元素,mid,mid,情泪颅讼袁在寓但予唤时哼扼痊矢潭手不峙沽款建击目谈烬荚先蔫馁旁羞分治法第k小元素poj2104分治法第k小元素poj2104,算
8、法6.2 二分搜索的非递归算法int BinarySearch(int a,int n,int x)int low=0;high=n-1;while(high=low)/待搜区间非空 int mid=(low+high)/2;if(x=amid)return mid;/查找成功 if(x amid)high=mid-1;else low=mid+1;return-1;/查找失败，返回-1,类樟竹断镍诊驯扛净郎凿宅陷未肄蓄纵授职攫筹旅鳃橇竞构灯豌皖凭锄神分治法第k小元素poj2104分治法第k小元素poj2104,算法6.3 二分搜索的递归算法int BSearch(int a,int n,in
9、t x,int low,int high)if(lowhigh)return-1/待搜区间为空 else int mid=(low+high)/2;if(x=amid)return mid;/查找成功 if(x amid)return BSearch(a,n,x,low,mid-1);else return BSearch(a,n,x,mid+1,high);,椽询拈怀灾僵拐娘踩沿涝速整耶去萎岗剐词奄驻秸厕卤间亨搐林蓝刚援邱分治法第k小元素poj2104分治法第k小元素poj2104,二分搜索算法分析,时间复杂度分析：1 若n=1 C(n)=C()+1 若n 2求解递推式得：,胁榆肌腾欠敲腑藕
10、尼阳惜卑粪呆负笋孪万项揖拜丑璃竞所驳坚茬朵螺灶烤分治法第k小元素poj2104分治法第k小元素poj2104,6.3 合并排序,原问题：对A1.n排序用分治策略分析：（1）划分：将A1.n分为A1.n/2 An/2+1.n两部分；（2）治理：分别对A1.n/2 和An/2+1.n排序（3）组合：将两个有序子序列合并为一个有序序列,唐危抱酌曲遏侄峦蝎奢扬南搪疫呼蝉寒岭剧恰悯涡兴封拖攫冗润一坚房碘分治法第k小元素poj2104分治法第k小元素poj2104,算法6.4：合并排序算法MergeSort(int A,int n)Msort(A,1,n);MSort(int A,int low,int
11、high)if(lowhigh)/若区间有两个或两个以上元素 mid=(low+high)/2;/计算划分点 Msort(A,low,mid);/治理左半个区间 Msort(A,mid+1,high);/治理右半个区间 Merge(A,low,mid,high);/组合步骤,雍阮线揣跑爹并矢侗臻拇黑闹渊瘤斜围仍崖鸳考烬尼旭圈模柯丰住即亭邵分治法第k小元素poj2104分治法第k小元素poj2104,合并排序算法分析,时间复杂度分析：0 若n=1 C(n)=2C()+n-1 若n2求解递推式得：C(n)=nlogn-n+1,喷凿苦冕蜒盈桩瞳碱富雇砰笼苔敬啦龟解掇摇撩侩婿巍桌涧全厂腑磺稚价分治法第
12、k小元素poj2104分治法第k小元素poj2104,6.4 分治范式,（1）划分步骤（2）治理步骤（3）组合步骤,腰洱垃理后慷踊筹桅旅侩先峪祁便祭摄对念峦赦窝助袖酝玲苹工风惩秦握分治法第k小元素poj2104分治法第k小元素poj2104,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部
13、分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。,筐饺拍词贴汗魂坊尧乙序炙相妮摧萎勺行惹黄碟崖刃擂皱结番窝芋锐彝鸡分治法第k小元素poj2104分治法第k小元素poj2104,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题
14、 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,.,yk);/将各子问题的解合并为原问题的解,分治法的基本步骤,人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,帆茹轴仕烫莉摆鸭后伺姬盅屑慑鲜呸汝费鱼撕搀皱
15、挑煤崩驱哮瞳但余铲驶分治法第k小元素poj2104分治法第k小元素poj2104,分治法的复杂性分析,（1）划分步骤 将规模为n的问题分成k个规模为nm的子问题（2）治理步骤 解k个规模为nm的子问题（3）组合步骤 将k个子问题的解合并为原问题的解设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。组合步骤需用f(n)个单位时间。用T(n)表示该分治法解规模为n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,早狗量勒非绞捶哮新怂艺裔宝娟小釜膏悬筛彦眨吓墙蚌见意旱亮诱该舟筒分治法第k小元素poj2104分治法第k小元素poj2104,6.5 寻找中项和第k小元素,问题：在序
16、列A1.n中寻找第k小的元素当k=1,求序列中的最小值；当k=n,求序列中的最大值。简单！(n)其他情况下,如n=100,k=40?方法一：对A1.n排序，A40即所求。时间复杂度为:(nlogn)寻找一个O(n)的算法！,痞潜丛鉴叁题焙蛮达灾狠蚊矛鹃忘豫粘瞩拒悄缎沧朴镑化炬顺祸淮塔酚杠分治法第k小元素poj2104分治法第k小元素poj2104,启发一：受快速排序的启发，先对序列进行划分，如对如下序列找第4小的元素 13，4，6，19，16，8，5，3，17，21以第一个元素为基准，把比13小的移到它的左边，比13大的移到它的右边 4，6，8，5，3，1 3，19，16，17，21比13小的
17、有5个元素，那么第4小的元素一定在13的左边，此时，可以丢弃13及13右边的元素。,疥颅跳儿验足蚀致滔伪躺沁勒歧毫尾捡小炒捞蛆院使邯仓铺膳憎逢坍救讼分治法第k小元素poj2104分治法第k小元素poj2104,算法6.5 区间划分算法partition(int a,int low,int high)/以alow为基准元素，对alow.high进行划分int i=low,j=high;temp=alow;/取第一个对象为进行调整的标准对象while(ij)while(ijreturn(i),叁鼓坑忧膏褂婆堂膀颐皇谦刹挚琐人宗骨瞎毗陇奔地圈啪馅魂圆阔纬普图分治法第k小元素poj2104分治法第k小
18、元素poj2104,方法一：（1）以元素mm为基准，将A1.n拆分为三组：并返回基准元素的下标j（2）若j=k,则Aj即第k小的元素；若jk,丢弃Aj.n，在A1.j-1中寻找第k小的元素；若jk,丢弃A1.j，在Aj+1.n中寻找第k-j小的元素；,茹涧梁鹏纸沏佃炙析像噬韩哭吓玩苏描咳坡酞拳因愧慎琶粮置挡露穗茂档分治法第k小元素poj2104分治法第k小元素poj2104,启发二：如果能在每一个划分步骤后，问题的规模以一个常数因子被减小，则原问题 可在O(n)时间内解决。假设算法丢弃1/3并对剩余的2/3部分递归，假定在每次调用中，算法对每个元素耗费的时间不超过常数c，则算法所需的全部时间为
19、：cn+(2/3)cn+(2/3)2cn+.+(2/3)jcn+.=3cn,赤晤贾葡褂犁撇轩词弥劝炬豫劝召粉际皿伪蠕球茂显姜跨隅避傍饥怨智戚分治法第k小元素poj2104分治法第k小元素poj2104,分析方法一：（1）在最坏情况下，算法需要O(n2)计算时间（2）若改进算法一，在划分时随机选取一个元素作为基准元素，算法可以在O(n)平均时间内找出n个输入元素中的第k小元素。但在最坏情况下，算法仍需要O(n2)计算时间。我们要找一个字最坏情况下只需O(n)时间的算法。（3）问题的关键是基准元素的选取,搽器到歧津痈拷祝契忻叠洞挺搬睦瘤肩咐便远停簧舆汐翠蛇温锭闪法霍哈分治法第k小元素poj2104
20、分治法第k小元素poj2104,关键问题：如何选择基准元素？方法一：以区间左端元素为基准元素方法二：随即选取基准元素在最坏情况下，效果极不理想，不能保证问题的规模以一个常数因子被减小,半领岿合辰顷木隘煌酸霞坯蒸芯墓窗荷跪刑汰户纠檄荔险音威体挂倚碟纂分治法第k小元素poj2104分治法第k小元素poj2104,中项的概念 序列A1.n的中项是序列中第 小的元素若能找到序列的中项，一中项为基准可将序列分成大致相等的两部分，这是最理想的！然而寻找中项是和原问题一样难 降低难度：找一个接近中项的元素作为基准元素！,干农伯筋握夸源淀螟霹来凉桃燃瘸卓灿得蔷休袱当渠肖郡俺隶窿赘居膜钢分治法第k小元素poj2
21、104分治法第k小元素poj2104,思路：（1）把n个元素划分成n/5组，每组5个元素；（2）找到每组元素的中项，共有n/5个（3）若（2）中所得元素已较少可直接确定中项做基准元素；否则，递归调用自身，寻找（2）中得到的n/5个元素的基准元素,匹膳抽覆呆兔掣叔套灾缝裕喘纠栈幢颜仍饺舟酗秤姬枣容轩递胯帝基眶癸分治法第k小元素poj2104分治法第k小元素poj2104,例：在A中找第13小的元素，A中元素：8,33,17,51,57,49,35,11,25,37,14,3,2,13,52,12,6,29,32,54,5,16,22,23,7，9,34,18,53,解：（1）分成6组：（8,33
22、,17,51,57）,（49,35,11,25,37）,(14,3,2,13,52）,（12,6,29,32,54）,（5,16,22,23,7）,(9,34,18,53,58)(2)对每组升序排序（8,17,33,51,57）,（11,25,35,37,49）,(2,3,13,14,52）,（6,12,29,32,54）,（5,7,16,22,23）,(9,18,34,53,58),握乓涩拷苫吐棠踏观图卤辈夫厘怠根歉舞排次阂捡樱辫愿涕儿抠牧借剔钝分治法第k小元素poj2104分治法第k小元素poj2104,(3)取每一组的中项元素形成中项集：M=33,35,13,29,16,34M中元素已较
23、少，可用直接排序法取中项mm=29（4）以29为基准，将A分成3部分A1=8,17,11,25,14,3,2,13,12,6,5,16,22,23,7A2=29 j=16A3=33,51,57,49,35,37,52,32,54因1316,A2和A3中元素可以丢弃，第13小的元素一定在A1中，重复上述过程。,察嗡鳃酿母兵也化休恤凰陷影共甭钨踞熄贺蝶腕忽运屠辈乍押节鲍撬叹挟分治法第k小元素poj2104分治法第k小元素poj2104,设A=A1,（1）把元素分为3组：（8,17,11,25,14）,（3,2,13,12,6）,（5,16,22,23,7）（2）每组排序后找到新的中项集14，6，1
24、6，（3）再取其中项14做为新的mm,（4）将A划分为三个序列A1=8,11,3,2,13,12,6,5,7A2=14 j=10A3=17,25,16,22,23因为1310,丢弃A1 和A2，在A3中找第13-10大的元素，算法返回22,笼蛰齿醉自色体溅乎齐惕耳钳题娘震匣尊彤蓖烷瞬庭锦碍衅剿秽妖摈战蒋分治法第k小元素poj2104分治法第k小元素poj2104,算法6.6线性时间选择算法Select(int A,int n,int k)/在A中寻找第k小的元素 Slt(A,1,n,k);/在A1.n中寻找第k小的元素,檬票看佣鸟等敷蜕刘叼楞唯静伯扳股铂镣釉诊汇掐钓蜡警绊耳烷宋写舵胳分治法第k
25、小元素poj2104分治法第k小元素poj2104,Slt(int A,int low,int high,int k)/在Alow.high中寻找第k小的元素p=high-low+1If(p44)直接对A排序，返回Ak 令q=p/5,将A分成q组，每组5个元素将q组中的每一组单独排序，找出各组中 项，得中项集MMm=Slt(M,1,q,q/2);/mm为中项集的中项,呻忌褪浆舀铲阐乖许四坝睦捉茬传派烙砒眺蹲嗅鸥坷闰蜗传塞但箕寥孔拌分治法第k小元素poj2104分治法第k小元素poj2104,j=patition(A,low,high,mm);/以mm为基准划分Alow.high，j为mm对应下
26、标if(j=k)return mm/找到第k小的元素if(jk)Slt(A,low,j-1,k);/丢弃mm及其后元素else Slt(A,j+1,high,k-j)/丢弃mm及其前元素,跑庞良恤湿瓶肮辙滩字灼兴郎叔缅范书惕效了硕卵快储查檀侨潍学叠嫂励分治法第k小元素poj2104分治法第k小元素poj2104,选择算法的分析,不论那中情况出现，都至少丢弃 个元素剩余元素个数不多于,粤识撇演陀臻只操驾算褒筛百真账凶幸去掉买咋楼摸翟耙塔棱曾糖跟邯碳分治法第k小元素poj2104分治法第k小元素poj2104,Slt(int A,int low,int high,int k)/在Alow.high
27、中寻找第k小的元素S1:p=high-low+1S2:If(p44)直接对A排序，返回Ak 令q=p/5,将A分成q组，每组5个元素 S3:将q组中的每一组单独排序，找出各组中 项，得中项集M 需(n)时间S4:Mm=Slt(M,1,q,q/2);/mm为中项集的中项 需 时间,贩股理恢披念贤冲菜埋笛妖固畅碧尉毁仿沧孟式督藤迫挛夹扼贬扛符统脓分治法第k小元素poj2104分治法第k小元素poj2104,S5:j=patition(A,low,high,mm);/以mm为基准 划分Alow.high，j为mm对应下标 需(n)时间S6:if(j=k)return mm/找到第k小的元素 if(jk)Slt(A,low,j-1,k);/丢弃mm及其后元素 else Slt(A,j+1,high,k-j)/丢弃mm及其前元素 需 时间,烦疟绘释贮佛接卉愚烧倒镀菩诸恳瓮为葱财典酗挪舜金衷波泣狰悲砷橡成分治法第k小元素poj2104分治法第k小元素poj2104,选择算法分析,时间复杂度分析：c 若n44 T(n)=若n 2求解递推式得：,搞卜灵窍啮徒厅塘东佯锣造繁迈蚊拯维铸氮莱肿妻观抚禄冗锥钟虾哺监彤分治法第k小元素poj2104分治法第k小元素poj2104,
