欢迎来到天天文库
浏览记录
ID:34571465
大小:198.39 KB
页数:34页
时间:2019-03-08
《麻省理工大学算法导论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
此文档下载收益归作者所有