版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
IntroductiontoAlgorithms
6.046J/18.401J
LECTURE1
AnalysisofAlgorithms
•Insertionsort
•Asymptoticanalysis
•Mergesort
•Recurrences
Prof.CharlesE.Leiserson
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
Courseinformation
1.Staff8.Coursewebsite
2.Distancelearning9.Extrahelp
3.Prerequisites10.Registration
4.Lectures11.Problemsets
5.Recitations12.Describingalgorithms
6.Handouts13.Gradingpolicy
7.Textbook14.Collaborationpolicy
September7,2005IntroductiontoAlgorithmsL1.2
Analysisofalgorithms
Thetheoreticalstudyofcomputer-program
performanceandresourceusage.
Whafsmoreimportantthanperformance?
modularity•user-friendliness
correctness•programmertime
maintainability•simplicity
functionality•extensibility
robustness•reliability
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.3
Whystudyalgorithmsand
、、7performance?
•Algorithmshelpustounderstandscalability.
•Performanceoftendrawsthelinebetweenwhat
isfeasibleandwhatisimpossible.
•Algorithmicmathematicsprovidesalanguage
fbrtalkingaboutprogrambehavior.
•Performanceisthecurrencyofcomputing.
•Thelessonsofprogramperformancegeneralize
toothercomputingresources.
•Speedisfun!
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.4
ALGORITHMS
Theproblemofsorting
Input:sequence〈%,%夕・・・,%〉°fnumbers.
Output:permutation*,…,such
f
thata\<a\<--<an.
Example:
Input:824936
Output:234689
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.5
ALGORITHMS
.0mmmD
Insertionsort
rINSERTION-SORT(A,n)>A[1..n]
for/<—2ton
dokey^A[j]
“pseudocode"\ijj—1
whilei>0andA[i]>key
doA[i+1]A[i]
i«-z—1
A\i+\}=key
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.6
ALGORITHMS
.0mmmD
Insertionsort
rINSERTION-SORT(A,n)>A[1..n]
for/<—2ton
dokey^A[j]
“pseudocode"\ijj—1
whilei>0andA[i]>key
doA[i+1]A[i]
i«-z—1
A\i+\}=key
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.7
ALGORITHMS
V_____
:、、,Exampleofinsertionsort
824936
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.8
ALGORITHMS
V_____
:、、,Exampleofinsertionsort
824936
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.9
ALGORITHMS
V_____
:、、,Exampleofinsertionsort
824936
284936
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.10
ALGORITHMS
:、、♦Exampleofinsertionsort
824936
284936
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.11
ALGORITHMS
V_____
Exampleofinsertionsort
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.12
Exampleofinsertionsort
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.13
Exampleofinsertionsort
6
6
6
6
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.14
Exampleofinsertionsort
6
6
6
6
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.15
ALGORITHMS
Exampleofinsertionsort
824936
284936
*—
248936
6
6
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.16
ALGORITHMS
Exampleofinsertionsort
824936
284936
*—
248936
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.17
ALGORITHMS
V_____
:、、,Exampleofinsertionsort
824936
284936
248936
234689done
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.18
ALGORITHMS
:、「Runningtime
•Therunningtimedependsontheinput:an
alreadysortedsequenceiseasiertosort.
•Parameterizetherunningtimebythesizeof
theinput,sinceshortsequencesareeasierto
sortthanlongones.
•Generally,weseekupperboundsonthe
runningtime,becauseeverybodylikesa
guarantee.
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.19
ALGORITHMS
.—
:、、,Kindsofanalyses
Worst-case:(usually)
•T(n)=maximumtimeofalgorithm
onanyinputofsizen.
Average-case:(sometimes)
•T(n)=expectedtimeofalgorithm
overallinputsofsizen.
•Needassumptionofstatistical
distributionofinputs.
Best-case:(bogus)
•Cheatwithaslowalgorithmthat
worksfastonsomeinput.
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.20
ALGORITHMS
Machine-independenttime
Whatisinsertionsort'sworst-casetime?
•Itdependsonthespeedofourcomputer:
•relativespeed(onthesamemachine)5
•absolutespeed(ondifferentmachines).
BIGIDEA:
•Ignoremachine-dependentconstants.
•LookatgrowthofT(n)as〃一oc.
^AsymptoticAnalysis^
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.21
ALGORITHMS
©-notation
Math:
0(g(n))={/(〃):thereexistpositiveconstantsc19c2,and
n0suchthat0<Cjg(n)</(n)<c2g(n)
fbralln>n0}
Engineering:
•Droplow-orderterms;ignoreleadingconstants.
•Example:3"+90/—5〃+6046=0(^3)
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.22
ALGORITHMS
:、、,Asymptoticperformance
Whenngetslargeenough,a0(zz2)algorithm
alwaysbeatsa0(H3)algorithm.
•Weshouldn'tignore
asymptoticallyslower
algorithms,however.
•Real-worlddesign
situationsoftencallfora
carefulbalancingof
engineeringobjectives.
•Asymptoticanalysisisa
usefultooltohelpto
structureourthinking.
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.23
ALGORITHMS
Insertionsortanalysis
Worstcase:Inputreversesorted.
n
T(〃)=[arithmeticseries]
六2
Averagecase:Allpermutationsequallylikely.
n
-(〃)=£。(〃2)=®伍2)
j=2
Isinsertionsortafastsortingalgorithm?
•Moderatelyso,forsmalln.
•Notatall,forlargen.
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.24
ALGORITHMS
,Mergesort
MERGE-SORTA[1..n\
1.If/z=1,done.
2.Recursivelysort4[1..「〃/2]]
andA[[n/2~\+l..n].
"Merge"the2sortedlists.
Keysubroutine:MERGE
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.25
ALGORITHMS
、、、、Mergingtwosortedarrays
2012
1311
79
21
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.26
ALGORITHMS
、、、、Mergingtwosortedarrays
2012
1311
79
y
1
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.27
ALGORITHMS
.annxnxxxD
Mergingtwosortedarrays
2012III2012
13111311
7979
芋|2
1
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.28
ALGORITHMS
Mergingtwosortedarrays
20122012
13111311
7979
2TT
12
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.29
ALGOMTHMS
.annxnnrc
Mergingtwosortedarrays
2012
1311
79
i2
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.30
Mergingtwosortedarrays
201220
131113
127
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.31
Mergingtwosortedarrays
20122012
13111311
9
1
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.32
Mergingtwosortedarrays
20122012
13111311
1279
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.33
Mergingtwosortedarrays
201212
11
27
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.34
Mergingtwosortedarrays
20122012
1311
12711
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.35
Mergingtwosortedarrays
201220122012
131113
111
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.36
ALGORiTHJvlS
.amxxnxnD
Mergingtwosortedarrays
20122012
1311
11112
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.37
ALGORITHMS
.ami™
Mergingtwosortedarrays
1112
Time=0(77)tomergeatotal
ofnelements(lineartime).
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.38
ALGORITHMS
Analyzingmergesort
T®MERGE-SORT^4[1..n\
「6⑴1.If扑=19done.
(2T(〃/2)2.Recursivelysort4[1..「〃/21]
Abuse/and/[[n/2~]+l..n].
/。⑺
3.“Merge”the2sortedlists
Sloppiness:ShouldbeT(「〃/2])+T(5/2」),
butitturnsoutnottomatterasymptotically.
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.39
ALGORITHMS
Recurrenceformergesort
r0(i)if/?=i;
T(〃)=
Y、2T(〃/2)+05)if〃>1.
•Weshallusuallyomitstatingthebase
casewhen7\n)=0(1)fbrsufficiently
smalln,butonlywhenithasnoeffecton
theasymptoticsolutiontotherecurrence.
•CLRSandLecture2provideseveralways
tofindagoodupperboundonT(n).
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.40
ALGORITHMS
Recursiontree
SolveT(n)=2T(M2)+cn,wherec>0isconstant.
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsL1.41
ALGORITHMS
Recursiontree
SolveT(n)=2T(M2)+cn,wherec>0isconstant.
丁⑺
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.42
ALGORITHMS
.U一3
二,Recursiontree
SolveT(n)=2T(n/2)+cn,wherec>0isconstant.
cn
T(〃/2)T(〃/2)
Copyright©2001-5Erik.D.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.43
ALGORITHMS
Recursiontree
SolveT(n)=2T(M2)+cn,wherec>0isconstant.
cn
cn/2cn/2
//、
T(T?/4)T(M4)T(TI/4)T(〃/4)
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.44
ALGORITHMS
Recursiontree
Solver(n)=2T(M2)+cn.wherec>0isconstant.
cn/4cnJ4c〃/4cnl4
©(1)
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.45
ALGORITHMS
Recursiontree
Solver(n)=2T(M2)+cn.wherec>0isconstant.
"—1g"cn14cnl4cn/4cn/4
©(1)
Copyright©2001-5ErikD.DemaineandCharlesE.Leiserson
September7,2005IntroductiontoAlgorithmsLI.46
ALGORITHMS
Recursiontree
SolveT(n)=2T(〃/2)+cn,wherec>0isconstant.
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 基于生活实践的小学语文阅读教学设计与实施策略探究
- 高中化学必修一全册课后优化训练:2-2-1 含解析
- 安全教育课教案
- 2025届青海省名校高三语文上学期9月考试卷附答案解析
- 汽车微控制器软件开发中的五大挑战-汽车制造商和供应商指南 2024
- 人教PEP版三年级英语上册课件 Revision
- DBXM137-2021肌张力障碍诊治规范
- 蜂窝物联网设备技术要求和测试方法
- 河北武邑中学2024-2025学年高三联合考试语文试题含解析
- 河北省衡水市衡水中学2025年高三3月初态测试语文试题试卷含解析
- 管理百年-知到答案、智慧树答案
- MOOC 宇宙简史-南京大学 中国大学慕课答案
- 七年级历史人教版历史第1单元测试题(含答案)
- 紧急避险课件 同正当防卫区别
- 困难群体心理关爱服务整体服务设想
- 急性胃粘膜病变护理查房
- JJG 603-2018频率表行业标准
- 2024年湖南湘潭钢铁集团有限公司招聘笔试参考题库附带答案详解
- 东北三省2023-2024高三上12月大联考数学试题和解析
- 基于信息化的项目式学习与学科教学融合实践研究项目申报书的课题设计论证
- 《五环旗下一家人》课件
评论
0/150
提交评论