版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、Chapter 2.Getting StartedOutlineFamiliarize you with the framework to think about the design and analysis of algorithmsIntroduce two sorting algorithms: insertion sort and merge sort Start to understand how to analyze the efficiency of algorithmsWe mainly concern about running time, or speed. Other
2、issues could also affect efficiency, e.g. memory, storage.Example: Sorting ProblemInput: A sequence of n numbersOutput: A permutation (reordering) of the input sequence such that PseudocodeDescribe algorithms as programs written in a pseudo codeEmploy whatever expressive method is most clear and con
3、cise to specify a given algorithmNot concerned with issues of software engineering, such as data abstraction, modularity and error handling Insertion SortIt is an efficient algorithm for sorting a small number of elementsIt works the way many people sort a hand of playing cardsIn insertion sort, the
4、 input numbers are sorted in place: the number are rearranged within the arrayInsertion SortFind an appropriate position to insert the new card into sorted cards in handsComparing and exchange in reverse orderProve the CorrectnessDesign, Prove and AnalyzeOften Use a loop invariantHow to define loop
5、invariant is importantE.g. for insertion sort:Loop invariant: At the start of each iteration of the “outer” for loop (line1-8)- the loop indexed by j - the sub-array A1 . . j-1 consists of the elements originally in A1 . j-1 but in sorted order.Loop InvariantTo use a loop invariant to prove correctn
6、ess, show three things about it:Initialization: It is true prior to the first iteration of the loop.Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.Termination: When the loop terminates, the invariantusually along with the reason that the loop te
7、rminatedgives us a useful property that helps show that the algorithm is correct.Analyzing algorithmsRandom-access machine(RAM) modelHow do we analyze an algorithms running time?The time taken by an algorithm depends on the input itself (e.g. already sorted)Input size: depends on the problem being s
8、tudied. (parameterize in input size)Want upper bound (guarantee to users)Running time: on a particular input, it is the number of primitive operations(steps) executed.RAM MODEL Do not model the memory hierarchyKinds of Analysis Worst-case (Usually) T(n)=max time on any input of size n Average-case (
9、Sometimes) T(n)=expected time over all input of size n How do we know the probability of every particular input is? I do not know. Make assumption of statistical distribution of inputs (what is the common assumption? ) Best-Case (bogus) Some slow algorithms work well on some input , cheating. Detail
10、ed Analysis of Algorithmn : the number of inputst j : the # of times the while loop test is executed.The loop test is executed one time more than the loop body.Thus, the running time of the above Insertion-Sort algorithm is:T(n) = c1n + c2(n-1) + c4(n-1) + c5 j=2 . n tj+ c6 j=2 . n(tj -1) + c7 j=2 .
11、 n(tj -1) + c8(n-1) = (c5/2 + c6/2 + c7/2) n2 + (c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8) n (c2+c4+c5+c8).t j : the # of times the while loop test is executed.The loop test is executed one time more than the loop body.Thus, the running time of the above Insertion-Sort algorithm is:T(n) = c1n + c2(n-1
12、) + c4(n-1) + c5 j=2 . n tj+ c6 j=2 . n(tj -1) + c7 j=2 . n(tj -1) + c8(n-1)Detailed Analysis of Running timeThis worst-case running time can be expressed as an2+bn+c , it is thus a quadratic functionAnalysis of Insertion SortThe running time of the algorithm is: (cost of statement) x ( # of times s
13、tatement is executed) all statementstj = # of times that while loop test is executed for that value of j.Best case: the array is already sorted (all tj = 1)Worst case: the array is in reverse order (tj = j).The worst case running time gives a guaranteed upper bound on the running time for any input.
14、Average case: On average, the key in A j is less than half the elements in A1 . j-1 and its greater than the other half. (tj = j /2).n(n-1)/2Order of Growth The abstraction to ease analysis and focus on the important features. Look only at the leading term of the formula for running time.Drop lower-
15、order terms.Ignore the constant coefficient in the leading term. Example: an + bn + c = (n)Drop lower-order terms anIgnore constant coefficient nThe worst case running time T(n) grows like n; it does not equal n.The running time is (n) to capture the notion that the order of growth is n.Order of gro
16、wth (2)We usually consider one algorithm to be more efficient than another if its worst-case running time has a lower order of growthDue to constant factors and lower-order terms, this evaluation may be error for small inputs but for large enough inputs, it is true.Designing algorithmsDivide and Con
17、querDivide the problem into a number of subproblems.Conquer the subproblems by solving them recursively.Base case: If the subproblems are small enough, just solve them.Combine the subproblem solutions to give a solution to the original problem.Cf.) Incremental method insertion sort.Merge SortA sorti
18、ng algorithm based on divide and conquer. The worst-case running time: Tmerge_sort the size of a subproblem.Use this technique when we analyze recursive algorithmLine 1-3 and 8-11 takes constant time and for loop takes (n1+n2) timeLoop Invariant of MERGELoop Invariant At the start of each iteration
19、of the for loop of lines 12-17, the subarray Apk-1 contains k-p elements of L1.n1+1 and R1. n2+1,in sorted order. Moreover, Li and Rj are the smallest elements of their arrays that have not been copied back into A.Show correctness using loop invariantWe show this loop invariant holds priori to the first iteration of the for loop and each iteration maintains the invariant and the invariant show correctness when the loop terminates.Loop InvariantInitialization Priori to the first iteration of the loop, we have k=p. Ap.k-1 is
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 《過敏性紫癜曹偉》課件
- 《代商務(wù)禮儀》課件
- 《確定市場調(diào)研目標(biāo)》課件
- 房屋租賃合同(2篇)
- 《硬盤使用前的處理》課件
- 2024年汽輪機(jī)油產(chǎn)品研發(fā)與技術(shù)轉(zhuǎn)移合作協(xié)議3篇
- 2025年鄭州貨運(yùn)從業(yè)資格證題庫
- 2025年昌都貨運(yùn)從業(yè)資格證考試模擬考試題庫下載
- 2024年混凝土構(gòu)件生產(chǎn)及安裝合同
- 2025年濟(jì)南道路運(yùn)輸從業(yè)人員從業(yè)資格考試
- 監(jiān)理公司各部門職責(zé)
- 253種中藥材粉末顯微鑒別主要特征
- 論辛棄疾詞作的愁情主題及其審美價(jià)值
- 新形勢下我國保險(xiǎn)市場營銷的現(xiàn)狀、問題及對(duì)策
- LTE無線網(wǎng)絡(luò)優(yōu)化PPT課件
- 動(dòng)態(tài)血壓監(jiān)測在社區(qū)高血壓患者管理的意義
- 管道中英文對(duì)照表
- 240燈控臺(tái)_說明書
- 新形勢下加強(qiáng)市場監(jiān)管局檔案管理工作的策略
- 例行檢查和確認(rèn)檢驗(yàn)程序
- 上海旅游資源基本類型及其旅游區(qū)布局特點(diǎn)(共5頁)
評(píng)論
0/150
提交評(píng)論