麻省理工大学算法导论lecture09

《麻省理工大学算法导论lecture09》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture9Prof.CharlesE.LeisersonBinary-search-treesortT←∅⊳CreateanemptyBSTfori=1tondoTREE-INSERT(T,A[i])PerformaninordertreewalkofT.Example:33A=[3182675]1188Tree-walktime=O(n),2266buthowlongdoesit5577taketobuildt

2、heBST?©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay17L9.2AnalysisofBSTsortBSTsortperformsthesamecomparisonsasquicksort,butinadifferentorder!3182675128675267557Theexpectedtimetobuildthetreeisasymptot-icallythesameastherunningtimeofquicksort.©2001byCha

3、rlesE.LeisersonIntroductiontoAlgorithmsDay17L9.3NodedepthThedepthofanode=thenumberofcomparisonsmadeduringTREE-INSERT.Assumingallinputpermutationsareequallylikely,wehaveAveragenodedepthn=1E∑()#comparisonstoinsertnodeini=1=1O(nlgn)(quicksortanalysis)n=O

4、(lgn).©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay17L9.4ExpectedtreeheightBut,averagenodedepthofarandomlybuiltBST=O(lgn)doesnotnecessarilymeanthatitsexpectedheightisalsoO(lgn)(althoughitis).Example.≤lgnh=n1n⋅nAve.depth≤n⋅lgn+n2=O(lgn)©2001byCh

5、arlesE.LeisersonIntroductiontoAlgorithmsDay17L9.5HeightofarandomlybuiltbinarysearchtreeOutlineoftheanalysis:•ProveJensen’sinequality,whichsaysthatf(E[X])≤E[f(X)]foranyconvexfunctionfandrandomvariableX.•AnalyzetheexponentialheightofarandomlybuiltBSTonnnodes,

6、whichistherandomvariableYXn,whereXn=2nistherandomvariabledenotingtheheightoftheBST.•Provethat2E[Xn]≤E[2Xn]=E[Y3),n]=O(nandhencethatE[Xn]=O(lgn).©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay17L9.6ConvexfunctionsAfunctionf:R→Risconvexifforallα,β≥0sucht

7、hatα+β=1,wehavef(αx+βy)≤αf(x)+βf(y)forallx,y∈R.ff(y)αf(x)+βf(y)f(x)f(αx+βy)xyαx+βy©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay17L9.7ConvexitylemmaLemma.Letf:R→Rbeaconvexfunction,andlet{α,α,…,α}beasetofnonnegative12nconstantssuchthat∑α=1.Then,foranys

8、etkk{x,x,…,x}ofrealnumbers,wehave12nnnf∑αkxk≤∑αkf(xk).k=1k=1Proof.Byinductiononn.Forn=1,wehaveα=1,andhencef(αx)≤αf(x)trivially.11111©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay17L9.8Pro