算法設(shè)計(jì)基本方法ppt課件-在線瀏覽
2025-06-29 12:54本頁(yè)面
【正文】 ???取 We just got lucky? 考察反推一步的誤差： ||1)1(1)1(1|| *1 NNNN ENININE ??????以此類(lèi)推，對(duì) n N 有： ||)1(...)1( 1|| Nn EnNNE ???誤差逐步遞減 , 這樣的算法稱(chēng)為 穩(wěn)定的算法 /* stable algorithm */ 類(lèi)似例子見(jiàn)教材 p8 算法設(shè)計(jì)基本方法（ 4） ? 遞歸 ? 將一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)較簡(jiǎn)單的問(wèn)題，然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)再歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程可以一直做下去，直到最簡(jiǎn)單的問(wèn)題為止。 result =1。 i = n。 } /* end if */ return result。 else return 1。 if (n= 1) return(1)。 } 算法效率：對(duì) F(n1) 、 F(n2)存在大量的重復(fù)計(jì)算 ? 改 進(jìn)：保存中間結(jié)果 例 :歐幾里得算法 已知兩個(gè)非負(fù)整數(shù) a和 b，且 a＞ b≥0 ，求這兩個(gè)數(shù)的最大公因數(shù)。 算法 求最大公因數(shù) GCD(int a,int b) // 約定 ab // { if (b==0) return(a)。 } 例： GCD(22,8) = GCD(8,6) = GCD(6,2) = GCD(2,0) = 2。所謂 “ 遞推 ” ，是指重復(fù) “ 減半 ” 的過(guò)程。 然后判斷 f(c)是否為 0。 最后判斷減半后的區(qū)間長(zhǎng)度是否已經(jīng)很小： 若 |a－ b|＜ ε，則過(guò)程結(jié)束，取 (a＋ b)/2為根的近似值； 若 |a－ b|≥ε，則重復(fù)上述的減半過(guò)程。 low=1。 while (low=high){ mid = if(xA[mid]) high=mid1。 else return mid。 } ? ?h ig h ) / 2( lo w ?注 ： 給定一個(gè)按非降次序排列的元素?cái)?shù)組 A(1:n)， n≥1,判斷 x是否出現(xiàn)。執(zhí)行軌跡見(jiàn)下表 1 表 1 運(yùn)行軌跡示例 x=101 x=14 x=82 low high mid low high mid low high mid 1 9 5 1 9 5 1 9 5 6 9 7 1 4 2 6 9 7 8 9 8 1 1 1 8 9 8 9 9 9 2 1 找不到 找到 找到 成功 的檢索 不成功 的檢索 成功 的檢索 遞推減半技術(shù) 特點(diǎn)：迅速縮小計(jì)算規(guī)模 適用范圍：工程計(jì)算，矩陣計(jì)算，數(shù)值計(jì)算中能夠迅速將問(wèn)題分治的情況 算法設(shè)計(jì)基本方法（ 6） ? 回溯法 ? 通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索，然后沿著這個(gè)線索逐步試探，對(duì)于每一步的試探，若試探成功，就得到問(wèn)題的解，若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。 算法分析是計(jì)算機(jī)領(lǐng)域的“古老”而“前沿”的課題。 算法 :即從數(shù)組的第一個(gè)元素開(kāi)始，逐個(gè)與被查值 x進(jìn)行比較。 平均性態(tài)分析 : 最壞情況分析 : W(n)＝ max{ti | 1≤i≤n＋ 1}＝ n 如何進(jìn)行算法分析？ 對(duì)算法進(jìn)行全面分析，可分兩個(gè)階段進(jìn)行： ?事前分析 ：求算法的一個(gè) 時(shí)間 /空間限界函數(shù) ，即通過(guò)對(duì)算 法的“理論”分析，得出關(guān)于算法 時(shí)間和空間特性 的特征函數(shù)（ Ο、 Ω） ——與計(jì)算機(jī)物理軟硬 件沒(méi)有直接關(guān)系。 1）事前分析 ? 目的：試圖得出關(guān)于算法特性的一種形式描 述（限界函數(shù)），以“理論上”衡量算法的“好壞”。 算法的執(zhí)行時(shí)間 =∑fi*ti ? 工作量 工作量 ：算法中 語(yǔ)句 或 運(yùn)算 的執(zhí)行次數(shù)。in。in。jn。 ? 分析手段：作時(shí)、空性能分布圖 計(jì)算時(shí)間的漸近表示 記：算法的實(shí)際計(jì)算時(shí)間為 f(n)，計(jì)算時(shí)間的限界函數(shù)為 g(n) 其中， ? n是輸入或輸出規(guī)模的某種測(cè)度。 ? g(n)是事前分析的結(jié)果 ——一個(gè) 形式簡(jiǎn)單 的函數(shù)，如 nm， logn，2n， n!等。 以下給出算法執(zhí)行時(shí)間： 上界 （ О）、 下界 （ Ω）、 “平均”（ ）的定義。所以 g(n)是計(jì)算時(shí)間 f(n)的一個(gè) 上界函數(shù) 。 ? 試圖求出 最小 的 g(n)，使得 f(n) = Ο(g(n))。 數(shù)量級(jí)反映了算法復(fù)雜度的最本質(zhì)的特征。次數(shù) 若 n=10，
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1