算法及其性能分析數(shù)據(jù)結構與算法

《算法及其性能分析數(shù)據(jù)結構與算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、Slide.2-1教學目的和內(nèi)容：§了解分析和評價算法的一些基本準則§掌握算法時間復雜性分析方法HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-2一、算法、算法的特征和算法描述算法（Algorithm）：是對特定問題求解步驟的一種描述，它是指令（規(guī)則）的有限序列，其中每一條指令表示一個或多個操作。算法的特征：①有窮性、②確定性、③能行性、④輸入、⑤輸出常用的算法設計方法：①遞歸法（Recursion）、②分治法(Divide-andConquer)、③貪心法(Greedy)、④動態(tài)規(guī)劃(D

2、ynamicProgramming)、⑤搜索與遍歷、⑥回溯（Backtracking）、⑦解空間局部搜索⑧近似算法(Approximation)、⑨在線算法（On-Line）等HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-3二、“好”的算法的標準1.正確性(Correctness)l正確性的含義：是指對于一切合法的輸入數(shù)據(jù)經(jīng)有限時間或有限步后均可得到正確（滿足規(guī)格說明要求）的結果；l算法包括兩方面的內(nèi)容：①解決問題的方法；②實現(xiàn)這一方法的一系列指令(語句、步驟)l算法的正確性證明：①需要

3、一組相關的引理和定理，確認一個算法所使用的方法和公式的正確性；②在證明一系列的語句確實做了符合規(guī)定的動作。l算法的正確性的嚴格的形式化證明還未取得突破，還是一項令人生畏的工作。只有那些比較簡單的算法，其正確性才能被形式化證明。HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-4二、“好”的算法的標準2.時間復雜性(TimeComplexity)l如何計算和比較算法的執(zhí)行時間：⑴實驗測量法（實際執(zhí)行時間、執(zhí)行指令的條數(shù)）優(yōu)點：精確缺點：必須先運行根據(jù)算法編制的的程序；所得的時間統(tǒng)計量依賴于計算

4、機的硬件、軟件等環(huán)境因素，容易掩蓋算法本身的優(yōu)劣。HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-5二、“好”的算法的標準⑵事前分析(估計)法高級語言編寫的程序在計算機上運行時間取決于下列因素：①依據(jù)的算法本身選擇何種策略②問題的規(guī)模（輸入的規(guī)模，輸入的大?。Ｈ缜笏財?shù)問題③程序設計語言：算法的實現(xiàn)語言級別越高，執(zhí)行效率越低④編譯程序產(chǎn)生的機器代碼的質(zhì)量⑤及其執(zhí)行指令的速度③④⑤表明用絕對的時間單位衡量一個算法的效率是不適合的l算法的時間復雜性①認為一個特定的算法執(zhí)行時間(“運行工作量”的

5、大小)，只依賴于問題的規(guī)模，即算法執(zhí)行時間是問題規(guī)模的函數(shù)---T(n)HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-6二、“好”的算法的標準②由于算法的執(zhí)行時間是組成算法的控制結構（順序、分支和循環(huán)）和基本操作的綜合效果，因此從算法中選擇對于研究問題來說是基本的操作（基本運算）,把算法的基本操作的重復執(zhí)行的次數(shù)作為算法的時間度量③通常，我們并不關心T(n)的具體值，而是關心它的增長率,即T(n)隨問題規(guī)模n（是一個整數(shù)）的增大的變化趨勢（界限）④算法的復雜性定義算法中基本操作重復執(zhí)行的

6、次數(shù)是問題規(guī)模n的某個函數(shù)f（n），算法的時間度量記作T（n）=O（f（n））。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率不會超過f（n），稱為算法的漸近時間復雜性，簡稱時間復雜性。HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-7二、“好”的算法的標準3.空間復雜性(SpaceComplexity)l算法的空間復雜性是指算法在執(zhí)行過程中的存儲量需求l一個算法的存儲量需求除了存放算法本身所有的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還包括對數(shù)據(jù)進行操作的工作單元和存儲實現(xiàn)計算所需信息的輔助空間l

7、算法的存儲量需求與輸入的規(guī)模、表示方式、算法采用的數(shù)據(jù)結構、算法的設計以及輸入數(shù)據(jù)的性質(zhì)有關l算法的執(zhí)行的不同時刻，其空間需求可能是不同的l算法的空間復雜性是指算法在執(zhí)行過程中的最大存儲量需求l空間復雜性的漸近表示----空間復雜度T（n）=O（f（n））其中，n為問題的輸入規(guī)模HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-8二、“好”的算法的標準4.可讀性(Readability)l可讀性好的算法有助于設計者和和他人閱讀、理解、修改和重用l晦澀難懂的算法容易隱藏錯誤,而且還增加了閱讀算

8、法的難度l可讀性好的算法，常常也具有簡單性5.健壯性(Robustness)l當輸入數(shù)據(jù)非法時，能作出適當?shù)姆磻ㄈ鐚斎霐?shù)據(jù)進行語法檢查，提出修改輸入建議并提供重新輸入的機會），避免異常出錯6.一個好的算法還應該具有靈活性（Flexibility）、可重用性(Reuseabale)和自適應性(Adaptability)等HIT哈爾濱工業(yè)大學計算機科學與技術學院張巖CSTSlide.2-9一、算法的時間復雜性定義