精品文档（有翻译）1.TheO-notationprovidesanasymptoticupperbound.The-notationprovidesanasymptoticlowerbound.TheΘ-notationasymptoticallyafunctionformaboveandbelow.O型符号提供一个渐近的上限。Θ符号提供一个渐近下界。Θ-符号渐近函数形式的上方和下方。2.Torepresentaheapasanarray，therootoftreeisA[1],andgiventheindexiofanode,theindicesofitsparentParent(i){returni/2;}，leftchild,Left(i){return2*i;}，rightchild,right(i){return2*i+1;}.代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是左孩子右孩子3.Becausetheheapofnelementsisabinarytree,theheightofanynodeisatmost(lgn).因为n个元素的堆是一个二叉树，任意节点的树高最多是4.Inoptimizationproblems,therecanbemanypossiblesolutions.Eachsolutionhasavalue,andwewishtofindasolutionwiththeoptimal(minimumormaximum)value.Wecallsuchasolutionanoptimalsolutiontotheproblem.在最优化问题中，有很多可能的解，每个解都有一个值，我们希望找到一个最优解（最大或最小），我们称这个解为最优解问题。5.optimalsubstructureifanoptimalsolutiontotheproblemcontainswithinitoptimalsolutionstosubproblems.最优子结构中问题的最优解，至少包含它的最优解的子问题。6.AsubsequenceofXifthereexistsastrictlyincreasingsequence
ofindicesofXsuchthatforallj=1,2,...,k,wehavexi=zj.jLetX=andY=besequences,andletZ=beanyLCSofXandY.(1).Ifxm=yn,thenzk=xm=ynandZk-1isanLCSofXm-1andYn-1.(2).Ifxm≠yn,thenzk≠xmimpliesthatZisanLCSofXm-1andY.(3).Ifxm≠yn,thenzk≠ynimpliesthatZisanLCSofXandYn-1.7.Agreedyalgorithmalwaysmakesthechoicethatlooksbestatthemoment.Thatis,itmakesalocallyoptimalchoiceinthehopethatthischoicewillleadtoagloballyoptimalsolution.贪心算法经常需要在某个时刻寻找最好的选择。正因如此，它在当下找到希望中的最优选择，以便引导出一个全局的最优解。8.Thegreedy-choicepropertyandoptimalsub-structurearethetwokeyingredientsofgreedyalgorithm.贪心选择和最优子结构是贪心算法的两个重要组成部分。9.Whenarecursivealgorithmrevisitsthesameproblemoverandoveragain,wesaythattheoptimizationproblemhasoverlappingsubproblems.当一个递归算法一遍一遍的遍历同一个问题时，我们说这个最优化问题是重叠子问题。10.greedy-choicepropertyisagloballyoptimalsolutioncanbearrived。1欢迎下载精品文档atbymakingalocallyoptimal(greedy)choice.贪心选择性质是一个全局的最优解，这个最优解可以做一个全局的最优选择。V11.AnapproachofMatrixmultiplicationcandevelopeaΘ(4)-timealgorithmfortheall-pairsshortest-pathsproblemandthenimproveitsrunningtimetoΘ(VlgV).3一个矩阵相乘问题的解决可以一个时间复杂度算法的所有路径的最短路径问题，改进后的时间复杂度是。12.Floyd-Warshallalgorithm,runsinΘ(V3)timetosolvetheall-pairsshortest-pathsproblem.FW算法在时间复杂度下可以解决最短路径问题。13.TherunningtimeofQuickSortisO(n2)intheworstcase,andO(nlgn)intheaveragecase.快速排序的平均时间复杂度是O(nlgn)，最坏时间复杂度是O(n2)。14.TheMERGE(A,p,q,r)procedureinmergesorttakestimeΘ(n).MERGE在归并排序中所花费的时间是。15.Givenaweighted,directedgraphG=(V,E)withsourcesandweightfunctionw:E→R,theBellman-Fordalgorithmmakes|V|-1passesovertheedgesofthegraph.给一个带权重的有向图G=(V,E)，权重关系w:E→R,则theBellman-Ford算法需经过条边。16.TheBellman-FordalgorithmrunsintimeO(VE).Bellmanford算法的时间复杂度是。17.Adecisiontreerepresentsthecomparisonsmadebyacomparisonsort.Theasymptoticheightofanydecisiontreeforsortingnelementsis(nlgn).一个决策树代表一个比较类型，通过比较排序。N个元素的任意决策树的渐进高度是。True-falsequestions1.Analgorithmissaidtobecorrectif,forsomeinputinstance,ithaltswiththecorrectoutputF如果给一个算法输入一些实例，并且它给力正确的输出，则认识这个算法是正确的。2.InsertionsortalwaysbestmergesortF插入排序总是优越与归并排序。3.Θ(nlgn)growsmoreslowlythanΘ(n2).Therefore,mergesortasymptoticallybeatsinsertionsortintheworstcase.TΘ(nlgn)4.Currentlycomputersarefastandcomputermemoryisverycheap,wehavenoreasontostudyalgorithms.F5.InRAM(Random-AccessMachine)model,instructionsareexecutedwithconcurrentoperations.F6.Therunningtimeofanalgorithmonaparticularinputisthenumberofprimitiveoperationsor“steps”executed.T7.Quicksorts,havenocombiningstep:twosubarraysformanalready-sortedarray.T。2欢迎下载精品文档8.TherunningtimeofCountingsortisO(n+k).Buttherunningtimeofsortingis(nlgn).Sothisiscontradiction.F9.TheCountingsortisstable.T10.Intheselectionproblem,thereisaalgorithmoftheoreticalinterestonlywithO(n)worst-caserunningtime.T11.Divide-and-conqueralgorithmspartitiontheproblemintoindependentsubproblems,solvethesubproblemsrecursively,andthencombinetheirsolutionstosolvetheoriginalproblem.Incontrast,dynamicprogrammingisapplicablewhenthesubproblemsarenotindependent,thatis,whensubproblemssharesubsubproblems.T12.Indynamicprogramming,webuildanoptimalsolutiontotheproblemfromoptimalsolutionstosubproblems.T13.Thebest-caserunningtimeisthelongestrunningtimeforanyinputofsizen.F14.Whenweanalyzetherunningtimeofanalgorithm,weactuallyinterestedontherateofgrowth(orderofgrowth).T15.Thedynamicprogrammingapproachmeansthatitbreaktheproblemintoseveralsubproblemsthataresimilartotheoriginalproblembutsmallerinsize,solvethesubproblemsrecursively,andthencombinethesesolutionstocreateasolutiontotheoriginalproblem.T16.Insertionsortandmergesortbothusedivide-and-conquerapproach.F17.Θ(g(n))={f(n):thereexistpositiveconstantsc1,c2,andn0suchthat0≤c1g(n)≤f(n)≤c2g(n)foralln≥n0}18.Min-Heapssatisfytheheapproperty:A[Parent(i)]A[i]forallnodesi>1.F19.Forarrayoflengthn,allelementsinrangeA[n/2+1..n]areheaps.T20.Thetighterboundoftherunningtimetobuildamax-heapfromanunorderedarrayisn’tinlineartime.F21.ThecalltoBuildHeap()takesO(n)time,Eachofthen-1callstoHeapify()takesO(lgn)time,ThusthetotaltimetakenbyHeapSort()=O(n)+(n-1)O(lgn)=O(n)+O(nlgn)=O(nlgn).T22.QuickSortisadynamicprogrammingalgorithm.ThearrayA[p..r]ispartitionedintotwonon-emptysubarraysA[p..q]andA[q+1..r],AllelementsinA[p..q]arelessthanallelementsinA[q+1..r],thesubarraysarerecursivelysortedbycallstoquicksort.F23.Assumethatwehaveaconnected,undirectedgraphG=(V,E)withaweightfunctionw:E→R,andwewishtofindaminimumspanningtreeforG.BothKruskalandPrimalgorithmsuseadynamicprogrammingapproachtotheproblem.F24.Acut(S,V-S)ofanundirectedgraphG=(V,E)isapartitionofE.F25.Anedgeisalightedgecrossingacutifitsweightisthemaximum。3欢迎下载精品文档ofanyedgecrossingthecut.F26.Kruskal'salgorithmusesadisjoint-setdatastructuretomaintainseveraldisjointsetsofelements.T27.Optimal-substructurepropertyisahallmarkoftheapplicabilityofbothdynamicprogramming.T28.Dijkstra'salgorithmisadynamicprogrammingalgorithm.F29.Floyd-Warshallalgorithm,whichfindsshortestpathsbetweenallpairsofvertices,isagreedyalgorithm.F30.Givenaweighted,directedgraphG=(V,E)withweightfunctionw:E→R,letp=beashortestpathfromvertexv1tovertexvkand,foranyiandjsuchthat1≤i≤j≤k,letpij=bethesubpathofpfromvertexvitovertexvj.Then,pijisashortestpathfromvitovj.T31.Givenaweighted,directedgraphG=(V,E)withweightfunctionw:E→R,Ifthereisanegative-weightcycleonsomepathfromstov,thereexistsashortest-pathfromstov.F32.SinceanyacyclicpathinagraphG=(V,E)containsatmost|V|distinctvertices,italsocontainsatmost|V|-1edges.Thus,wecanrestrictourattentiontoshortestpathsofatmost|V|-1edges.T33.Theprocessofrelaxinganedge(u,v)testswhetherwecanimprovetheshortestpathtovfoundsofarbygoingthroughu.T34.InDijkstra'salgorithmandtheshortest-pathsalgorithmfordirectedacyclicgraphs,eachedgeisrelaxedexactlyonce.IntheBellman-Fordalgorithm,eachedgeisalsorelaxedexactlyonce.F35.TheBellman-Fordalgorithmsolvesthesingle-sourceshortest-pathsprobleminthegeneralcaseinwhichedgeweightsmustbenegative.F36.Givenaweighted,directedgraphG=(V,E)withsourcesandweightfunctionw:E→R,theBellman-FordalgorithmcannotreturnaBooleanvalueindicatingwhetherornotthereisanegative-weightcyclethatisreachablefromthesource.F37.Givenaweighted,directedgraphG=(V,E)withsourcesandweightfunctionw:E→R,fortheBellman-Fordalgorithm,ifthereissuchacycle,thealgorithmindicatesthatnosolutionexists.Ifthereisnosuchcycle,thealgorithmproducestheshortestpathsandtheirweights.F38.Dijkstra'salgorithmsolvesthesingle-sourceshortest-pathsproblemonaweighted,directedgraphG=(V,E)forthecaseinwhichalledgeweightsarenegative.F39.Dijkstra'salgorithmsolvesthesingle-sourceshortest-pathsproblemonaweighted,directedgraphG=(V,E)forthecaseinwhichalledgeweightsarenonnegative.Bellman-Fordalgorithmsolvesthesingle-sourceshortest-pathsproblemonaweighted,directedgraphG。4欢迎下载精品文档=(V,E),therunningtimeofDijkstra'salgorithmislowerthanthatoftheBellman-Fordalgorithm.T40.Thestepsfordevelopingadynamic-programmingalgorithm:1.Characterizethestructureofanoptimalsolution.2.Recursivelydefinethevalueofanoptimalsolution.3.Computethevalueofanoptimalsolutioninabottom-upfashion.4.Constructanoptimalsolutionfromcomputedinformation.T三Eachofninputelementsisanintegerintherange0tok,Designalinearrunningtimealgorithmtosortnelements.四Designaexpectedlinearrunningtimealgorithmtofindtheithsmallestelementofnelementsusingdivideandconquerstrategy.五WritetheINSERT-SORTproceduretosortintonon-decreasingorder.AnalyzetherunningtimeofitwithRAMModel.What’sthebest-caserunningtime,theworst-caserunningtimeandaveragecaserunningtime.WritetheMERGE-SORTproceduretosortintonon-decreasingorder.Givetherecurrencefortheworst-caserunningtimeT(n)ofMergesortandfindthesolutiontotherecurrence.六WhatisanoptimalHuffmancodeforthefollowingsetoffrequencies,七Thetraveling-salesmanproblem(TSP):inthetraveling-salesmanproblem,wearegivenacompleteundirectedgraphG=(V,E)thathasanonnegativeintegercostc(u,v)associatedwitheachedge(u,v)E,andwemustfindatourofGwithminimumcost.ThefollowingisaninstanceTSP.Pleasecomputeatourwithminimumcostwithgreedyalgorithm.14216214251322599161962396八Givenitemsofdifferentvaluesandweights,findthemostvaluablesetofitemsthatfitinaknapsackoffixedweightC.Foraninstanceofknapsackproblem,n=8,C=110,valueV={11,21,31,33,43,53,55,65}weightW={1,11,21,23,33,43,45,55}.Usegreedyalgorithmstosolveknapsackproblem.九UsedynamicprogrammingtosolveAssembly-lineschedulingproblem:AMotorsCorporationproducesautomobilesthathastwoassemblylines,numberedi=1,2.Eachlinehasnstations,numberedj=1,2…n.WedenotethejthstationonlineibyS.Thefollowingfigureisaninstanceofijtheassembly-lineproblemwithcostsentrytimee,exittimex,theiiassemblytimerequiredatstationSbya,thetimetotransferachassisijij。5欢迎下载精品文档awayfromassemblylineIafterhavinggonethroughstationSist.ijijPleasecomputethefastesttimeandconstructthefastestwaythroughthefactoryoftheinstance.7934842323134entranceexit2122142856457十.Thematrix-chainmultiplicationproblemcanbestatedasfollows:givenachainofmatrices,wherefori=1，2…，n,matrixAihasdimensionPP,fullyparenthesizetheproductA,A,…,Ainawaythatminimizesi-1i12nthenumberofscalarmultiplication.WepickasoursubproblemstheproblemsofdeterminingtheminimumcostofaparenthesizationofAiAi+1Ajfor1≤i≤j≤n.Letm[i,j]betheminimumnumberofscalarmultiplicationsneededtocomputethematrixAi..j;forthefullproblem,thecostofacheapestwaytocomputeA1..nwouldthusbem[1,n].Canyoudefinem[i,j]recursively?Findanoptimalparenthesizationofamatrix-chainproductwhosesequenceofdimensionsis<4,3,5,2,3>十一Inthelongest-common-subsequence(LCS)problem,wearegiventwosequencesX=andY=andwishtofindamaximum-lengthcommonsubsequenceofXandY.PleasewriteitsrecursiveformulaanddetermineanLSCofSequenceS1=ACTGATCGandsequenceS2=CATGC.Pleasefillintheblanksinthetablebelow.CATGCACTGATCG。6欢迎下载精品文档十二Proof:AnycomparisonsortalgorithmrequiresΩ(nlgn)comparisonsintheworstcase.Howmanyleavesdoesthetreehave?（叶节点的数目）–Atleastn!(eachofthen!permutationsiftheinputappearsassomeleaf)⇒n!≤l（至少n!个，排列）–Atmost2hleaves（引理，至多2h个）⇒n!≤l≤2h⇒h≥lg(n!)=Ω(nlgn)十三Proof:Subpathsofshortestpathsareshortestpaths.Givenaweighted,directedgraphG=(V,E)withweightfunctionw:E→R,letp=beashortestpathfromvertexvtovertexv12k1kand,foranyiandjsuchthat1≤i≤j≤k,letp=beijii+1jthesubpathofpfromvertexvtovertexv.Then,pisashortestpathijijfromvtov.ij十四Proof:TheworstcaserunningtimeofquicksortisΘ(n2)十五ComputeshortestpathswithmatrixmultiplicationandtheFloyd-Warshallalgorithmforthefollowinggraph.十六WritetheMAX-Heapify()proceduretoformanipulatingmax-heaps.AndanalyzetherunningtimeofMAX-Heapify().三（10分)1CountingSort(A,B,k)2fori=1tok3C[i]=0;4forj=1ton5C[A[j]]+=1;6fori=2tok7C[i]=C[i]+C[i-1];。7欢迎下载精品文档8forj=ndownto19B[C[A[j]]]=A[j];10C[A[j]]-=1;四算法描述3分Thebest-caserunningtimeisT(n)=cn+c(n-1)+c(n-1)+c(n-12451)+c(n-1)8=(c+c+c+c+c)n-(c+c+c+c).Thisrunningtimecanbeexpressed124582458asan+bforconstantsaandbthatdependonthestatementcostsc;iitisthusalinearfunctionofn.Thisworst-caserunningtimecanbeexpressedasan2+bn+cforconstantsa,b,andcthatagaindependonthestatementcostsc;itisthusaiquadraticfunctionofn.
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
2分算法描述2分Θ(1)ifn=1T(n)=2T(n/2)+Θ(n)ifn>1.。8欢迎下载精品文档递归方程和求解3分五7RAND-SELECT(A,p,r,i)(5分)ifp=rthenreturnA[p]q←RAND-PARTITION(A,p,r)k←q–p+1ifi=kthenreturnA[q]ifi10055a:453025d:1614c:12b:1330f:5e:9a:1b:100c:101d:111e:1100f:1101八V={11,21,31,33,43,53,55,65}weightW={1,11,21,23,33,43,45,55}1121313343535565按照单位重量的价值排序，，然后按照该顺111212333434555序往背包中放。九递归方程4分f1[1]=9f2[1]=12。10欢迎下载精品文档f1[2]=18f2[2]=16f1[3]=20f2[3]=22f1[4]=24f2[4]=25f1[5]=32f2[5]=30f1[6]=35f2[6]=37thefastesttimeis38andthefastestwayis:station1:line1station2:line2station3:line1station4:line2station5:line2station6:line1求解过程6分十递归方程4分m[1,1]=0m[2,2]=0m[3,3]=0m[4,4]=0m[1,2]=m[1,1]+m[2,3]+p0*p1*p2=60m[2,3]=m[2,2]+m[3,3]+p1*p2*p3=30m[3,4]=m[3,3]+m[4,4]+p2*p3*p4=30m[1,3]=min{m[1,2]+m[3,3]+p0*p2*p3,m[1,1]+m[2,3]+p0*p1*p3}=54m[2,4]=min{m[2,3]+m[4,4]+p1*p3*p4,m[2,2]+m[3,4]+p0*p2*p4}=48m[1,4]=min{m[1,1]+m[2,4]+p0*p1*p4,m[1,2]+m[3,4]+p0*p2*p4,m[1,3]+m[4,4]+p0*p3*p4}=78((A1(A2A3))A4)求解过程6分十一c[i1,j1]1ifx[i]y[j],c[i,j]max(c[i,j1],c[i1,j])otherwise递归方程4分CATGC000000A001111C011112T011222G011233A011233T011234C011234G。11欢迎下载精品文档最长公共子序列长度为4AGTC求解过程6分十二Fromtheprecedingdiscussion,itsufficestodeterminetheheightofadecisiontreeinwhicheachpermutationappearsasareachableleaf.Consideradecisiontreeofheighthwithlreachableleavescorrespondingtoacomparisonsortonnelements.从前面讨论,它可以确定一个决策树的高度,每个排列显示为一个可到达的叶子。考虑一个决策树的高度h和l可及的叶子在n个元素对应于一种比较。Becauseeachofthen!permutationsoftheinputappearsassomeleaf,因为每个n!排列的输入出现一些叶子,wehaven!≤l.Sinceabinarytreeofheighthhasnomorethan2hleaves,因为一个二叉树的高度h没有超过2h叶子wehave（分析5分）n!≤l≤2h,which,bytakinglogarithms,implieshlg(n!)(sincethelgfunctionismonotonicallyincreasing)=(nlgn)列式和求解5分十三Proof:Ifwedecomposepathpintovvvv,thenwehavethatw(p)1ijk=w(p)+w(p)+w(p).Now,assumethatthereisapathp’fromvto1iijjkijivwithweightw(p’)A[i])largest=l;elselargest=i;if(r<=heap_size(A)&&A[r]>A[largest])largest=r;if(largest!=i)Swap(A,i,largest);Heapify(A,largest);}Fixinguprelationshipsbetweeni,l,andrtakes(1)time，Iftheheapatihasnelements,thesubtreesatlorrcanhave2n/3elements.SotimetakenbyHeapify()isgivenbyT(n)T(2n/3)+(1),byrecursivetree,thesolutionisT(n)=O(lgn).算法描述4分列递归方程3分，求解3分。14欢迎下载
浙公网安备 33021202002483