麻省理工大学算法导论lecture14

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

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture14Prof.CharlesE.LeisersonHowlargeshouldahashtablebe?Goal:Makethetableassmallaspossible,butlargeenoughsothatitwon’toverflow(orotherwisebecomeinefficient).Problem:Whatifwedon’tknowthepropersizeinadvance?Solution:Dynamictables.IDEA:Wheneverthetableov

2、erflows,“grow”itbyallocating(viamallocornew)anew,largertable.Moveallitemsfromtheoldtableintothenewone,andfreethestoragefortheoldtable.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.2Exampleofadynamictable1.INSERT12.INSERToverflow©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.3E

3、xampleofadynamictable1.INSERT112.INSERToverflow©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.4Exampleofadynamictable1.INSERT112.INSERT2©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.5Exampleofadynamictable1.INSERT112.INSERT223.INSERToverflow©2001byCharlesE.LeisersonIntroductio

4、ntoAlgorithmsDay24L14.6Exampleofadynamictable1.INSERT12.INSERT23.INSERToverflow©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.7Exampleofadynamictable1.INSERT12.INSERT23.INSERT©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.8Exampleofadynamictable1.INSERT12.INSERT23.INSERT34.INSE

5、RT4©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.9Exampleofadynamictable1.INSERT12.INSERT23.INSERT34.INSERT45.INSERToverflow©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.10Exampleofadynamictable1.INSERT12.INSERT23.INSERT34.INSERT45.INSERToverflow©2001byCharlesE.LeisersonIntro

6、ductiontoAlgorithmsDay24L14.11Exampleofadynamictable1.INSERT12.INSERT23.INSERT34.INSERT45.INSERT©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.12Exampleofadynamictable1.INSERT12.INSERT23.INSERT34.INSERT45.INSERT56.INSERT67.INSERT7©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay24L14.1

7、3Worst-caseanalysisConsiderasequenceofninsertions.Theworst-casetimetoexecuteoneinsertionisΘ(n).Therefore,theworst-casetimeforninsertionsisn·Θ(n)=Θ(n2).WRONG!Infact,theworst-casecostforninsertionsisonl