算法設(shè)計基本方法ppt課件-wenkub
2023-05-27 12:54:55 本頁面
【正文】 營長對值班軍官 : 明晚大約 8點鐘左右，哈雷彗星將可能在這個地區(qū)看到，這種彗星每隔 76年才能看見一次。如果下雨的話，就讓士兵穿著野戰(zhàn)服列隊前往禮堂，這一罕見的現(xiàn)象將在那里出現(xiàn)。如果下雨的話，營長將命令彗星穿上野戰(zhàn)服到操場上去。 方法：先估計一個 IN ,再反推要求的 In ( n N )。 if ( n 0 ) { for ( i = 1。 } int factorial ( int n ) { if ( n 0 ) return n * factorial ( n ? 1 )。 else return F(n1) + F(n2)。 else return (GCD(b,a % b))。 例：二分法求方程實根的減半遞推過程（算法及程序見書 p13） 首先取給定區(qū)間的中點 c＝ (a＋ b)/2。 例 二分檢索 二分檢索：每次選取 中間元素 的下標(biāo) 算法 二分檢索 Int BINSRCH(int A[],int n,int x) { int low,high,mid。 if(xA[mid]) low =mid+1。 ?若是，返回當(dāng)前角標(biāo) mid ?若非，返回 0，表示沒有找到 例：設(shè) A(1:9)=(15， 6， 0， 7， 9， 23， 54， 82， 101) 在 A中檢索 x=101， 14， 82。 算法分析 ? “好”的算法應(yīng)當(dāng)達(dá)到以下指標(biāo) ? 正確性 (Correctness):算法應(yīng)當(dāng)滿足具體問題的需求 ? 可讀性 (Readability):算法是連接數(shù)學(xué)模型和程序的橋梁 ,可讀性好有助于人對算法的理解 ? 健壯性 (Robustness):算法對于異常情況有充分的考慮和處理方法 ? 效率高和存儲量少 : ? 時間復(fù)雜度 :指執(zhí)行算法所需要的計算工作量 算法的工作量＝ f(n) ? 空間復(fù)雜度 :執(zhí)行算法所需要的內(nèi)存空間 n指算法規(guī)模 時間復(fù)雜度 (1) ? 平均性態(tài) (average behavior): ? 用各種特定輸入下的基本運算次數(shù)的帶權(quán)平均值來度量算法的工作量 ? 最壞情況復(fù)雜性 (WorstCase Complexity) ? 規(guī)模在 n時 ,算法所執(zhí)行的基本運算的最大次數(shù) ???nDxxtxpnA )()()( )}({m a x)( xtnWnDx ??由于最壞情況復(fù)雜性給出算法工作量的一個上界 ,所以更具實用價值 時間復(fù)雜度 (2) ? 例 :順序搜索法的時間復(fù)雜度分析 (教材 p17) 采用順序搜索法，在長度為 n的一維數(shù)組中查找為 x的元素。 ?事后測試 ：將算法編制成程序后實際放到計算機上運行， 收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進(jìn)行 分析判斷 ——直接與物理實現(xiàn)有關(guān)。 例： x=x+y for (i=0。i++) x = x + y for (j=0。 ? f(n)表示算法的“實際”執(zhí)行時間 —與機器及語言有關(guān) 。 ?1）上界函數(shù) 定義 1 如果存在兩個正常數(shù) c和 n0，對于所有的 n≥n 0，有 |f(n)| ≤ c|g(n)| 則記作 f(n) = Ο(g(n)) 含義： ? 如果算法用 n值不變的同一類數(shù)據(jù)在某臺機器上運行時，所用的時間總是小于 |g(n)|的一個常數(shù)倍。 ? 數(shù)量級 —— 衡量 工作量 的“ 大小 ”的一種測度，通過 f(n)的上界函數(shù) g(n)確定 ? 語句的數(shù)量級 ：語句的執(zhí)行次數(shù) 例： 1， n ， n2 ? 算法的數(shù)量級 ：算法所包含的所有語句的執(zhí)行次數(shù)之和。 計算時間的 數(shù)量級的大小對算法有 決定性 的影響 例：假設(shè)解決同一個問題的兩個算法，它們都有 n個輸入 , 計算時間的數(shù)量級分別是 n2和 nlogn。 多項式時間算法 和 指數(shù)時間算法 ? 多項式時間算法 ：可用多項式（函數(shù)）對其計算時間限界 的算法。 ? 要想在順序處理機上擴大所處理問題的規(guī)模，有效的途徑 是 降低算法的計算復(fù)雜度 ，而不是（僅僅依靠）提高計算 機的速度。 2）下界函數(shù) 定義 如果存在正常數(shù) c1， c2和 n0，對于所有的 n≥n 0，有 c1|g(n)| ≤|f(n)| ≤ c 2|g(n)| 則記作 含義： ? 算
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1