《算法與算法分析》ppt課件-文庫吧
2025-04-14 03:58 本頁面
【正文】 及到軟件工程原理 目標 2涉及到數(shù)據(jù)結(jié)構(gòu)與算法分析 本課程主要講的是與目標 2有關的問題 怎樣度量算法的代價、效率呢？ 19 怎樣比較兩種算法解決問題的效率呢？ ? 實驗比較 – 用源程序分別實現(xiàn)這兩種算法，然后輸入適當?shù)臄?shù)據(jù)運行，測算兩個程序各自的開銷 – 這是一種事后統(tǒng)計的方法 ? 漸近算法分析 (asymptotic algorithm analysis)， 簡稱 算法分析 (algorithm analysis) – 可以估算出當問題規(guī)模變大時，一種算法及實現(xiàn)它的程序的效率和開銷 – 這是一種事前分析估算的方法 20 “ 規(guī)模 ” 與 “ 基本操作 ” ? 判斷算法性能的一個基本考慮是處理一定 “ 規(guī)模 ” (size)的輸入時該算法所需執(zhí)行的 “ 基本操作 ” (basic operation)數(shù) ? “ 規(guī)模 ” 一般是指輸入量的數(shù)目 – 比如，在排序問題中，問題的規(guī)?？梢杂帽慌判蛟氐膫€數(shù)來衡量 21 “ 規(guī)模 ” 與 “ 基本操作 ” （續(xù)） ? 一個 “ 基本操作 ” 必須具有這樣的性質(zhì)：完成該操作所需時間與操作數(shù)的具體取值無關 – 在大多數(shù)高級語言中，下列操作是基本操作： ? 賦值運算 ? 簡單算術運算 ? 簡單布爾運算 ? 簡單 I／ O操作 ? 函數(shù)返回 – n個整數(shù)累加不是基本操作 ? 因為其代價依賴于 n的值 (即大小 ) 22 運行時間和增長率 ? 由于影響運行時間的最主要因素一般是輸入的規(guī)模，所以經(jīng)常把執(zhí)行算法所需要的時間 T寫成輸入規(guī)模 n的函數(shù)，記為 T(n) – 我們總是假設 T(n)為非負值 ? 算法的 增長率 (growth rate)是指當輸入規(guī)模增長時，算法代價的增長速率 23 最佳、最差和平均情況 不是相同規(guī)模的所有輸入的運行時間都相同 順序搜索法（ Sequential search） 從一個 n元一維數(shù)組中找出一個給定的值 K : ? 從第一個元素開始，依次檢索每一個元素，直到找到 K為止 最佳情況 : 最差情況 : 平均情況 : 24 請用 通俗的例子 談談 對 增長率 和 平均情況 兩個概念的理解 請郵件告訴我（ ） 25 Growth Rate Graph 26 時間復雜性（續(xù)） 更快的計算機，還是更快的算法 ? 27 時間復雜度對解題速度的影響 O(n) 解 題 速 度 n = 10 n = 30 n = 60 n ms ms ms n2 ms ms ms n5 s s min 2n ms min 世紀 3n s 年 1013 世紀 28 ? 阿達爾定律 設 f 為求解某個問題的計算存在的必須串行執(zhí)行的操作占整個計算的百分比， p 處理機的數(shù)目， Sp 為并行計算機系統(tǒng)最大的加速能力（單位：倍），則 設 f =1%， p ? ?， 則 Sp =100。 串行計算與并行計算 pffS p???1129 算法分析的任務是對設計出的每一個具體的算法，利用數(shù)學工具，討論其復雜度，探討具體算法對問題的適應性 ? 算法的時間復雜度 ? 規(guī)模 ? 基本操作 ? 增長率 ? 平均情況 ? 效率 請把下列的術語融入到上句中， 對算法分析的任務進行更加清晰的說明 30 漸近分析 :大 O 定義 : 對于非負函數(shù) T(n)， 若存在兩個正常數(shù)c和 n0， 使得當 nn0時有 T(n)≤cf(n)， 則稱T(n)在集合 O(f(n))中。 用法 : 這個算法 [最佳、平均、最差 ]情況（下的增長率的上限）在 O(n2)中 . 含意 : 對于問題的所有 [最佳、平均、最差情況 ]輸入，只要輸入規(guī)模足夠大 (即 nn0), 該算法總能在 cf(n) 步以內(nèi)完成 . 31 上限 :大 O (cont
教學課件相關推薦
鄂ICP備17016276號-1