MIT計算機開放課

上傳人：浪*** IP屬地：河北上傳時間：2023-12-29 格式：PDF 頁數(shù)：52 大小：5.64MB 積分：12 舉報 版權(quán)申訴

已閱讀5頁，還剩47頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

IntroductiontoAlgorithms

6.046J/18.401J

LECTURE1

AnalysisofAlgorithms

?Insertionsort

?Asymptoticanalysis

?Mergesort

?Recurrences

Prof.CharlesE.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

September7,2005IntroductiontoAlgorithmsL1.3

Whystudyalgorithmsand

、、7performance?

?Algorithmshelpustounderstandscalability.

?Performanceoftendrawsthelinebetweenwhat

isfeasibleandwhatisimpossible.

?Algorithmicmathematicsprovidesalanguage

fbrtalkingaboutprogrambehavior.

?Performanceisthecurrencyofcomputing.

?Thelessonsofprogramperformancegeneralize

toothercomputingresources.

?Speedisfun!

September7,2005IntroductiontoAlgorithmsLI.4

ALGORITHMS

Theproblemofsorting

Input:sequence〈%,%夕???，％〉°fnumbers.

Output:permutation*，…，such

thata\<a\<--<an.

Example:

Input:824936

Output:234689

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

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

September7,2005IntroductiontoAlgorithmsL1.7

ALGORITHMS

V_____

：、、，Exampleofinsertionsort

824936

September7,2005IntroductiontoAlgorithmsL1.8

ALGORITHMS

V_____

：、、，Exampleofinsertionsort

824936

September7,2005IntroductiontoAlgorithmsL1.9

ALGORITHMS

V_____

：、、，Exampleofinsertionsort

824936

284936

September7,2005IntroductiontoAlgorithmsLI.10

ALGORITHMS

：、、?Exampleofinsertionsort

824936

284936

September7,2005IntroductiontoAlgorithmsLI.11

ALGORITHMS

V_____

Exampleofinsertionsort

September7,2005IntroductiontoAlgorithmsLI.12

Exampleofinsertionsort

September7,2005IntroductiontoAlgorithmsLI.13

Exampleofinsertionsort

September7,2005IntroductiontoAlgorithmsLI.14

Exampleofinsertionsort

September7,2005IntroductiontoAlgorithmsLI.15

ALGORITHMS

Exampleofinsertionsort

824936

284936

*—

248936

September7,2005IntroductiontoAlgorithmsLI.16

ALGORITHMS

Exampleofinsertionsort

824936

284936

*—

248936

September7,2005IntroductiontoAlgorithmsLI.17

ALGORITHMS

V_____

：、、，Exampleofinsertionsort

824936

284936

248936

234689done

September7,2005IntroductiontoAlgorithmsLI.18

ALGORITHMS

：、「Runningtime

?Therunningtimedependsontheinput:an

alreadysortedsequenceiseasiertosort.

?Parameterizetherunningtimebythesizeof

theinput,sinceshortsequencesareeasierto

sortthanlongones.

?Generally,weseekupperboundsonthe

runningtime,becauseeverybodylikesa

guarantee.

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.

September7,2005IntroductiontoAlgorithmsLI.20

ALGORITHMS

Machine-independenttime

Whatisinsertionsort'sworst-casetime?

?Itdependsonthespeedofourcomputer:

?relativespeed(onthesamemachine)5

?absolutespeed(ondifferentmachines).

BIGIDEA:

?Ignoremachine-dependentconstants.

?LookatgrowthofT(n)as〃一oc.

^AsymptoticAnalysis^

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)

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.

September7,2005IntroductiontoAlgorithmsLI.23

ALGORITHMS

Insertionsortanalysis

Worstcase:Inputreversesorted.

T(〃)=[arithmeticseries]

六2

Averagecase:Allpermutationsequallylikely.

-(〃)=￡。(〃2)=?伍2)

j=2

Isinsertionsortafastsortingalgorithm?

?Moderatelyso,forsmalln.

?Notatall,forlargen.

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

September7,2005IntroductiontoAlgorithmsLI.25

ALGORITHMS

、、、、Mergingtwosortedarrays

2012

1311

September7,2005IntroductiontoAlgorithmsL1.26

ALGORITHMS

、、、、Mergingtwosortedarrays

2012

1311

September7,2005IntroductiontoAlgorithmsLI.27

ALGORITHMS

.annxnxxxD

Mergingtwosortedarrays

2012III2012

13111311

7979

芋|2

September7,2005IntroductiontoAlgorithmsL1.28

ALGORITHMS

Mergingtwosortedarrays

20122012

13111311

7979

2TT

September7,2005IntroductiontoAlgorithmsLI.29

ALGOMTHMS

.annxnnrc

Mergingtwosortedarrays

2012

1311

September7,2005IntroductiontoAlgorithmsL1.30

Mergingtwosortedarrays

201220

131113

127

September7,2005IntroductiontoAlgorithmsL1.31

Mergingtwosortedarrays

20122012

13111311

September7,2005IntroductiontoAlgorithmsL1.32

Mergingtwosortedarrays

20122012

13111311

1279

September7,2005IntroductiontoAlgorithmsL1.33

Mergingtwosortedarrays

201212

September7,2005IntroductiontoAlgorithmsL1.34

Mergingtwosortedarrays

20122012

1311

12711

September7,2005IntroductiontoAlgorithmsL1.35

Mergingtwosortedarrays

201220122012

131113

111

September7,2005IntroductiontoAlgorithmsL1.36

ALGORiTHJvlS

.amxxnxnD

Mergingtwosortedarrays

20122012

1311

11112

September7,2005IntroductiontoAlgorithmsL1.37

ALGORITHMS

.ami?

Mergingtwosortedarrays

1112

Time=0(77)tomergeatotal

ofnelements(lineartime).

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.

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).

September7,2005IntroductiontoAlgorithmsLI.40

ALGORITHMS

Recursiontree

SolveT(n)=2T(M2)+cn,wherec>0isconstant.

September7,2005IntroductiontoAlgorithmsL1.41

ALGORITHMS

Recursiontree

SolveT(n)=2T(M2)+cn,wherec>0isconstant.

?、?/p>

September7,2005IntroductiontoAlgorithmsLI.42

ALGORITHMS

.U一3

二，Recursiontree

SolveT(n)=2T(n/2)+cn,wherec>0isconstant.

T(〃/2)T(〃/2)

September7,2005IntroductiontoAlgorithmsLI.43

ALGORITHMS

Recursiontree

SolveT(n)=2T(M2)+cn,wherec>0isconstant.

cn/2cn/2

//、

T(T?/4)T(M4)T(TI/4)T(〃/4)

September7,2005IntroductiontoAlgorithmsLI.44

ALGORITHMS

Recursiontree

Solver(n)=2T(M2)+cn.wherec>0isconstant.

cn/4cnJ4c〃/4cnl4

?(1)

September7,2005IntroductiontoAlgorithmsLI.45

ALGORITHMS

Recursiontree

Solver(n)=2T(M2)+cn.wherec>0isconstant.

"—1g"cn14cnl4cn/4cn/4

?(1)

September7,2005IntroductiontoAlgorithmsLI.46

ALGORITHMS

Recursiontree

SolveT(n)=2T(〃/2)+cn,wherec>0isconstant.

人人文庫> 全部分類> 教育資料 > 輔導(dǎo)培訓(xùn)

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

MIT計算機開放課

文檔簡介

溫馨提示

最新文檔

評論

MIT計算機開放課

文檔簡介

溫馨提示

最新文檔

評論

相關(guān)文檔