2023年算法实验报告分治法性能分析

2023年算法实验报告分治法性能分析２023年算法实验报告分治法性能分析古小费20１１-3-2９本次是第一次算法作业，该部分内容包含3个题目的程序代码，分析文档，说明图片等内容

目录TOC＼ｏ"1－3"＼h\z\uHYPERLINK\ｌ＂_Ｔoc２8919８677＂引言 PAＧEＲEF_Toc28９198６77\h3ＨＹＰERLINK\l"＿Toc28９19867８"1算法性能比较ﻩPＡGEREF_Ｔoc2891９8６7８\h3ＨYＰEＲLＩNK1．1问题分析ﻩＰＡGEＲEF_Toc28９1986７9\h３HYPERLINK＼l"_Tｏc28９198680＂1.2源程序代码 PAGＥREF_Tｏｃ２891986８0\h3HYPERLINＫ\l＂_Toc289１986８1"1.3运行示例 PAＧEREF＿Ｔｏc２89198６８1＼ｈ8HYPＥＲLIＮK\l"_Toｃ28９1９8６82"1.4数据分析ﻩPＡGＥREＦ_Toc2891９8６82\h8HYPERＬＩNK\l"_Tｏc2891９8683"(单次录入数据具有较大随机误差,只看增长趋势）ﻩPAＧEREＦ_Ｔoc２８919８６８３\h8HＹPERLIＮＫ＼l"_Toｃ28９１98684"２循环赛问题 PAＧERＥF＿Toｃ289198684\h9ＨYPERＬIＮＫ\l"_Tｏｃ2891９8６8５"２.1问题描述 ＰAGＥＲEF_Tｏc２89198685\ｈ9HYPERLINK＼l"_Ｔoc28９１986８６"2.2问题分析 ＰAGERＥF_Toc289１98６86\h９HＹＰＥRLINK2.3源程序 ８7\ｈ１02.４运行示例 ＰAＧEREF_Toc2８9198６88\ｈ1１HＹＰERLＩNK3最大最小值问题ﻩ１986８9\h12ＨYPＥＲＬＩＮK＼l"_Toｃ2891986９0"3.１问题描述与分析ﻩPAＧEＲＥＦ＿Toｃ289１98６９０\h１２HＹPＥＲLINK3．2源程序ﻩPＡＧERＥF＿Toｃ289１98691\h１3HＹPＥRＬINＫ3.3运行示例 ＰAGＥREF＿Toc2891９8６92\h14引言任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题的规模越小，越容易直接求解，解题所需的计算时间也越少。分治法是计算机科学中经常使用的一种算法。设计思想是，将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。但是不是所有问题都适合用分治法解决。当求解一个输入规模为n且取值又相称大的问题时，使用蛮力策略效率一般得不到保证。因此分治策略将问题划提成ｋ个子问题分别求解合并能有效提高计算效率。１算法性能比较1.１问题分析比较插入排序，合并排序和快速排序性能。算法性能比较通常是从时间复杂度的角度进行的。排序算法的复杂度重要和算法中的比较次数和元素互换或移动次数有关。因而在不同大小规模的问题中通过记录这两者之和来评判算法的优劣。同时也可以证明各种算法的时间复杂度与问题规模n之间的关系。特别说明：本程序中考虑到不同规模的乱序数据输入过程比较复杂,编写了一个规模n的整型数据随机排列函数，可以直接生成指定大小的1-ｎ无序整数列。1.2源程序代码//2023年3月19日0：20：02//maｉnｔｅst.cｐpfoｒtest#incｌｕde<iｏstream>#inclｕde<tiｍe．h＞usinｇnamｅsｐａcesｔd;//全局标记比较次数和移动次数inｔcoｕｎｔ＿compare=0；iｎtｃoｕnt_movｅ＝0;ｉntｃｏｕnt＿aｌl(){rｅturncｏuｎt_cｏmpａre+counｔ_ｍoｖe;｝voidｃleａｒ_cｏｕｎｔ(){ｃount＿ｃｏmpａrｅ=０;count_move＝0;}／/iｎseｒtsｏrｔvｏidinsｅrt_elｅｍeｎt（ｉnｔa［],intsiｚe,inteｌemenｔ)//sizeｂeforeinsｅｒtｉon{inｔi=0;for(ｉ=siｚe－1;i>=0;i-－){ｃoｕnt_ｃomparｅ＋+；if(eleｍent<ａ［i］)｛a[ｉ+１]=a[i];count_movｅ++;}ｅｌsｅbｒｅａｋ;}a[i＋1］=elｅmｅnt;couｎｔ＿move++；}voidInｓｅrtＳort(inｔa[]，iｎtsize){foｒ(inti=1；i<size;ｉ＋+){iｎseｒt＿ｅlement(a,ｉ,ａ［ｉ］)；｝｝//merｇesｏrtｖoiｄMｅrｇｅ(ｉｎtc[],intｄ［］，ｉnｔｌ,iｎtｍ，iｎtｒ){inti=l,ｊ=m+１,k=ｌ;while(i<=m&＆ｊ<=ｒ)｛count_comｐare++；ｉｆ（c［i］<=ｃ［j］){ｄ［k+＋]=ｃ[i++];cｏｕｎt＿ｍoｖｅ++;}else{d[k＋+］＝ｃ[j+＋];counｔ＿ｍoｖｅ++;}}couｎt＿ｃｏmpaｒe++;if（ｉ＞m){ｆor（inｔq=j；q<=ｒ;q++)｛d[k+＋]＝c［q]；ｃoｕｎｔ_ｍoｖｅ＋+;}｝eｌsｅfor(inｔq＝i；ｑ<＝ｍ;q+＋){d[ｋ+＋]=c[q]；count＿moｖe＋+;｝｝voiｄCopy（inｔa[],ｉntb[],iｎtl，intr){ｆor（inｔi=ｌ;ｉ<=r；i++){a[i]=b[i]；ｃount_mｏve++；}}vｏｉdMｅｒgeSort(iｎｔa[],inｔlefｔ,iｎtright，intsize）｛iｆ（ｌｅft<riｇht){count_cｏｍpaｒe++;iｎti=(ｒｉght＋ｌeft)／2;intｐ＝sｉｚｅ;//thｉsｉsimｐｏrtａnt，mindthｅvａluｅ！int*b＝newint[p］;ＭergeSort（a,ｌeｆt,ｉ,size);MerｇeＳort(a,i+1,rｉgｈｔ,size);Mｅｒge(ａ,b,ｌeft,i，ｒighｔ）;Cｏpy（ａ，b,lefｔ,riｇht）;｝｝//quicksｏrtvoｉdｓwap(inta[],iｎｔi,inｔj){iｎtｔｅｍp=ａ[i];a［i]=a[j];ａ[ｊ］＝ｔｅｍp;ｃount＿move＋=3;}intpａrtiｔion(inｔａ［],ｉnｔp,intr){iｎtｉ=ｐ,j＝r+１;iｎtx=ａ[p];while(tｒue){while(a[++i]＜x&&ｉ<ｒ)ｃouｎt_coｍｐare＋+;whiｌe(ａ[-－j]>x)coｕnt_compaｒe＋+;ｃount_comｐare++;if(i>＝j)break;swap（a,ｉ,j）;}ａ［p]=a［j];a[j]=x;counｔ_moｖe＋+;retｕｒnｊ;}voidQuickSｏｒt(inta[],ｉntp，iｎｔr)｛iｆ(p<r）{iｎtq＝partitiｏn（a,p，r);QuiｃkＳoｒｔ(a，p，ｑ-１）；ＱuｉckSｏrt（a，ｑ+1,r）;}couｎｔ_cｏmｐare＋+;}//shｏwｖｏiｄshow_array(inta[],inｔｓiｚｅ)//显示一个数组的所有元素{ｆor(inti=０;ｉ<sizｅ;i++）{ｃoｕt<<a[i］＜<"";｝ｃout<<ｅndl；}/／ranｄｏmaｒraｙvoiｄRandoｍＡrrａｙ(ｉnta［],iｎtsizｅ)//随机生成数组含n个元素，其元素各不相同{srand(tｉme(NUＬL));fｏr(inti=0；ｉ<sｉzｅ;i++)a[i]=0;foｒ（inti＝1;i<=sｉze;i++){ｉntｐ＝rand（)％sｉze;wｈiｌｅ（ａ[p]!=0)｛p＝（++p）％ｓize;}a［p］＝ｉ；｝show_aｒray(a,size);}／/copｙａrrａyvoidＣopｙArｒａy(inta[]，ｉntｂ[]，ｉｎtsｉze）｛foｒ(inti=0;i<siｚe;i＋＋）b[i]=a[i];}intmaｉｎ()｛iｎｔ＊a；iｎt*temｐ＿a;ｉntsize＝４;cin>>size;a=ｎewint[ｓizｅ];teｍｐ_ａ=newint[size]；RandoｍArrａy(tｅmp_ａ,sｉｚe）；CopyＡrｒay(ｔemp_a,ａ，ｓize);show＿ａrｒay(a，size);IｎsｅrｔSｏｒt(a,siｚe);ｓhow＿aｒray(a,siｚe);cｏut<<"插入排序比较次数为"<<ｃouｎｔ_ｃｏmpare<<eｎｄｌ;ｃouｔ<<"插入排序移动次数为"＜＜ｃoｕnt＿moｖe<<eｎdl；cｏｕt<＜＂总规模为"<<count_all（)<<ｅnｄl;cleａr_ｃｏｕｎt（);CoｐyＡrraｙ（ｔｅmp＿ａ,a,sizｅ)；shｏw_array（ａ,size)；MergｅSort（a，0,ｓiｚｅ-1,sｉze）；show＿arｒay（a,ｓiｚe);coｕｔ<<＂合并排序比较次数为＂<＜coｕnｔ_compare＜＜endl;cout＜<＂合并排序移动次数为"<<count_move<<endｌ;coｕt<＜"总规模为"<<counｔ_alｌ()<＜ｅnｄｌ；clｅar_cｏunt();CopｙＡｒｒaｙ(tｅmｐ_ａ，ａ，sｉze）;show_array(a,sｉze);QuｉｃkSorｔ（a,０,size-1）；show_aｒray(ａ，siｚe);cｏut<<"快速排序比较次数为"<＜ｃoｕnt＿coｍparｅ<＜endｌ;coｕt<<"快速排序移动次数为＂＜<couｎt_mｏve<<endl;cｏut＜<"总规模为＂＜＜counｔ_ａll()<<endｌ;show_ａrrａy（a,size）;ｓysｔem("pause＂);retuｒn０;}}1．3运营示例1．4数据分析(单次录入数据具有较大随机误差，只看增长趋势）问题规模(n）排序总复杂度规模(Ｔ(n))插入排序合并排序快速排序１0571０5502０2２1280１223０3６74612３84０９4６6６037１5０13948７９4３２８0３２6１15７0８56１0046９4206４1064200２29１２4718244７50０１3０1３313６68７368100０５04254303091７0０31０000４389810３4019６8２254８９根据列表分析,插入算法平均复杂度为Ο（n2）,合并算法平均复杂度为Ο（nlogn），2循环赛问题2．１问题描述设有n个运动员要进行网球循环赛。设计一个满足下列条件的比赛日程表:每个选手必须与其他n-1个选手各赛一次；每个选手一天只能赛一次;当n是偶数时，循环赛进行n-1天。当n是奇数时,循环赛进行n天。2．2问题分析当ｎ=(ｋ=１、2、3、4,……,ｎ=２、4、８、16，……)时，此时问题比较简朴。按照分治的策略,可将所有参赛的选手分为两部分,n＝个选手的比赛日程表就可以通过为n／2=个选手设计的比赛日程表来决定。递归地执行这种分割，直到只剩下2个选手时,比赛日程表的制定就变得很简朴:只要让这2个选手进行比赛就可以了。再逐步合并子问题的解即可得到原问题的解。推广当n为任意整数时：当n小于或等于1时，没有比赛。当ｎ是偶数时,至少举行n-1轮比赛．当n是奇数时,至少举行n轮比赛,这时每轮将会有一支球队轮空。因此应对策略如下：(１)当ｎ／２为偶数时，与n=情形类似，可用分治法求解。（2)当ｎ/2为奇数时，递归返回的轮空的比赛要作进一步解决。可以在前n/2轮比赛中让轮空选手与下一个未参赛选手进行比赛。2.3源程序#inclｕde<iostreａm>usingnaｍｅspａcｅstd；intａ[100][100］;ｉntｂ[1０0];bｏolodd(intn)/／判断ｎ奇偶性{returnｎ&1;//ｎ为奇数,返回1，ｎ为偶数，返回0}vｏidcoｐyodd(intｎ）/／n/2为奇数时的合并算法{iｎtm=ｎ／2;for(ｉnｔi=0;ｉ<ｍ；ｉ＋+){b［i]＝m+i;b［m+ｉ]=b[ｉ］；｝ｆor(intｉ＝0；i<m;i++)｛／/由左上角小块的值算出相应的左下角小块的值for(intj=0;j<m＋1;j+＋){if（a[ｉ][j]>=m)｛a[ｉ][j]=ｂ[i]；a[m+i］[j]=(b[i］+m)%n；}elsea［ｍ+i][j]=a[ｉ］[j]＋m;｝//由左上角小块的值算出相应的右上角和右下角小块的值foｒ(iｎtj=1；ｊ＜m;j++){a[i][m+j]=ｂ[i＋j]；a[b［i+ｊ]][m+j］=i;}}｝voidcｏpy(ｉnｔn){iｎtm=n/2;ｆor(ｉnti=０;i<m;i+＋)ｆoｒ(iｎｔj=0；j<m；j＋+){／/由左上角小块的值算出相应的右上角小块的值a［i］［j+m]=a[i][j]＋m；//由右上角小块的值算出相应的左下角小块的值a[i+m][j]=a［i][j+m];//由左上角小块的值算出相应的右下角小块的值ａ［i+m][ｊ+m]=a[i][j]；}｝ｖｏidmakecｏpｙ(ｉnｔｎ)//合并算法{iｆ（(n／2)>1&&odd(n/2))ｃoｐｙｏdd(ｎ)；//ｎ/2为奇数时ｅlsecoｐｙ(ｎ）;}voiｄtournａ（iｎtｎ)/／改善的分治赛算法{ｉf（n==1){a[０][０]＝０;ｒeturｎ;}if(odｄ（ｎ)）{ｔourna（ｎ+1);return;}//ｎ为奇数,分治tｏurna(n/２);//n为偶数，分治ｍakecopy(n);/／合并｝inｔmaiｎ(){intｎ;cout<＜"请输入参数队数：＂<<endｌ;cin>>ｎ;tourna(n);cout<<＂参数日程表为：＂<＜endｌ;for(inti=0;ｉ<ｎ；i+＋){fｏr(ｉntj=０;j<n；j++)ｃｏuｔ<＜a[i][j］<＜＂";couｔ<<endl;}syｓｔem("pause");retuｒn0;｝2．４运营示例3最大最小值问题3.１问题描述与分析在具有n个不同元素的集合中同时找出它的最大和最小元素算法思想:先相邻两个两个比较,较大的放入数组max［]，较小的放入数组min[],然后从max[]数组求出最大，min[]数组求出最小即可。从算法描述中可以看出,占据算法的重要执行次数的是比较过程,因此算法的复杂性重要跟比较次数相关T当n是2的幂时,即对于某个正整数k，n=2kT(ｎ)＝2Ｔ(n／2)＋2=2(2T(ｎ／４)＋2)+2＝2*2T(ｎ/4）＋２＊2＋２….．=2k-1+2=3n/2-２这是最优情况，平均则比直接比较少25%3．2源程序／/findmaｘandmin#ｉｎclude＜iｏstreaｍ>usingｎａmespacｅstｄ；vｏidＭax＿Mｉn(intａ[］,intn){intm