算法分析算法复习题(中英文)

《算法分析算法复习题(中英文)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、（有翻译）1.TheO-notationprovidesanasymptoticupperbound.TheW-notationprovidesanasymptoticlowerbound.TheΘ-notationasymptoticallyafunctionformaboveandbelow.O型符号提供一个渐近的上限。Θ符号提供一个渐近下界。 Θ-符号渐近函数形式的上方和下方。2.Torepresentaheapasanarray，therootoftreeisA[1],andgiventheindexiofanode,theindicesofitsparentParent(

2、i){returnëi/2û;}，leftchild,Left(i){return2*i;}，rightchild,right(i){return2*i+1;}.代表一个堆中的一个数组，树的根节点是A[1]，并且给出一个节点i，那么该节点的父节点是左孩子右孩子3.Becausetheheapofnelementsisabinarytree,theheightofanynodeisatmostQ(lgn).因为n个元素的堆是一个二叉树，任意节点的树高最多是4.Inoptimizationproblems,therecanbemanypossiblesolutions.Eachsolu

3、tionhasavalue,andwewishtofindasolutionwiththeoptimal(minimumormaximum)value.Wecallsuchasolutionanoptimalsolutiontotheproblem.在最优化问题中，有很多可能的解，每个解都有一个值，我们希望找到一个最优解（最大或最小），我们称这个解为最优解问题。5.optimalsubstructureifanoptimalsolutiontotheproblemcontainswithinitoptimalsolutionstosubproblems.最优子结构中问题的最优解，至

4、少包含它的最优解的子问题。6.AsubsequenceofXifthereexistsastrictlyincreasingsequenceofindicesofXsuchthatforallj=1,2,...,k,wehavexij=zj.LetX=andY=besequences,andletZ=beanyLCSofXandY.(1).Ifxm=yn,thenzk=xm=ynandZk-1isanLCSofXm-1andYn-1.(2).Ifxm≠yn,thenzk≠

5、xmimpliesthatZisanLCSofXm-1andY.(3).Ifxm≠yn,thenzk≠ynimpliesthatZisanLCSofXandYn-1.7.Agreedyalgorithmalwaysmakesthechoicethatlooksbestatthemoment.Thatis,itmakesalocallyoptimalchoiceinthehopethatthischoicewillleadtoagloballyoptimalsolution.贪心算法经常需要在某个时刻寻找最好的选择。正因如此，它在当下找到希望中的最优选择，以便引导出一个全局的最优解。

6、8.Thegreedy-choicepropertyandoptimalsub-structurearethetwokeyingredientsofgreedyalgorithm.贪心选择和最优子结构是贪心算法的两个重要组成部分。9.Whenarecursivealgorithmrevisitsthesameproblemoverandoveragain,wesaythattheoptimizationproblemhasoverlappingsubproblems.当一个递归算法一遍一遍的遍历同一个问题时，我们说这个最优化问题是重叠子问题。10.greedy-choiceprop

7、ertyisagloballyoptimalsolutioncanbearrivedatbymakingalocallyoptimal(greedy)choice.贪心选择性质是一个全局的最优解，这个最优解可以做一个全局的最优选择。11.AnapproachofMatrixmultiplicationcandevelopeaΘ(V4)-timealgorithmfortheall-pairsshortest-pathsproblemandthenimproveitsr