算法設(shè)計基本方法ppt課件-文庫吧資料
2025-05-18 12:54本頁面
【正文】 的考慮和處理方法 ? 效率高和存儲量少 : ? 時間復雜度 :指執(zhí)行算法所需要的計算工作量 算法的工作量＝ f(n) ? 空間復雜度 :執(zhí)行算法所需要的內(nèi)存空間 n指算法規(guī)模 時間復雜度 (1) ? 平均性態(tài) (average behavior): ? 用各種特定輸入下的基本運算次數(shù)的帶權(quán)平均值來度量算法的工作量 ? 最壞情況復雜性 (WorstCase Complexity) ? 規(guī)模在 n時 ,算法所執(zhí)行的基本運算的最大次數(shù) ???nDxxtxpnA )()()( )}({m a x)( xtnWnDx ??由于最壞情況復雜性給出算法工作量的一個上界 ,所以更具實用價值 時間復雜度 (2) ? 例 :順序搜索法的時間復雜度分析 (教材 p17) 采用順序搜索法，在長度為 n的一維數(shù)組中查找為 x的元素。 例：八皇后問題（教材 p15）迷宮問題 實際上是一種圖的深度優(yōu)先遍歷的方法 特點：算法效率高，直觀清楚 適用范圍：適用于解決 “ 是否存在 ” 或者 “ 有多少種可能 ” 問題 缺點：算法的復雜性與計算順序有關(guān) 算法分析 1. 分析算法的目的 在于：通過對算法的分析，在把算法變成程序?qū)嶋H運行前，就知道為完成一項任務(wù)所設(shè)計的算法的好壞，從而運行好的算法，改進差的算法，避免無益的人力和物力浪費。 ?若是，返回當前角標 mid ?若非，返回 0，表示沒有找到 例：設(shè) A(1:9)=(15， 6， 0， 7， 9， 23， 54， 82， 101) 在 A中檢索 x=101， 14， 82。 } return 0。 if(xA[mid]) low =mid+1。 high=n。 例 二分檢索 二分檢索：每次選取 中間元素 的下標 算法 二分檢索 Int BINSRCH(int A[],int n,int x) { int low,high,mid。 若 f(c)＝ 0,則說明 c即為所求的根，求解過程結(jié)束； 如果 f(c)≠0,則根據(jù)以下原則將原區(qū)間減半： 若 f(a)f(c)＜ 0，則取原區(qū)間的前半部分； 若 f(b)f(c)＜ 0，則取原區(qū)間的后半部分。 例：二分法求方程實根的減半遞推過程（算法及程序見書 p13） 首先取給定區(qū)間的中點 c＝ (a＋ b)/2。 遞歸 特點：結(jié)構(gòu)清晰，可讀性強，容易用數(shù)學歸納法證明算法正確性 適用范圍：難以用循環(huán)或遞推直觀描述的復雜問題 缺點：資源耗費多，執(zhí)行效率低，所以在算法優(yōu)化時采用消遞歸策略 算法設(shè)計基本方法（ 5） ? 減半遞推技術(shù)（分治法） ? 所謂 “ 減半 ” ，是指將問題的規(guī)模減半，而問題的性質(zhì)不變。 else return (GCD(b,a % b))。 輾轉(zhuǎn)相除法 ：若 b=0，則 a和 b的最大公因數(shù)等于 a；若 b＞ 0，則 a和 b的最大公因數(shù)等于 b和用 b除 a的余數(shù)的最大公因數(shù)。 else return F(n1) + F(n2)。 } 例 :斐波那契 (Fibonacci)序列： F0 = F1 = 1 Fi = Fi1 + Fi2 （ i1) 算法 求斐波那契數(shù) int F(n) { //返回第 n個斐波那契數(shù) // int n。 } int factorial ( int n ) { if ( n 0 ) return n * factorial ( n ? 1 )。 i++ ) result = result * i 。 if ( n 0 ) { for ( i = 1。 例： 計算階乘 : n! = n(n?1) ? ? ? 2?1, 0! = 1. int factorial ( int n ) { int i, result。 方法：先估計一個 IN ,再反推要求的 In ( n N )。 ......2101 10 ,n,dxexeI xnn ?? ?例： 計算 11 ??? nn InI? 公式一： 632120560111 100 .edxeeI x ???? ?記為 *0I8000 1050 ?? ???? .IIE則初始誤差 111111 110010 ????????? ?? nI)e ( ndxexeIdxexe nnnn39 1 414 2 315195 9 42 49414122 7 64 80713163 2 89 60 0012103 0 59 20 0011108 8 12 80 00101............
教學課件相關(guān)推薦
鄂ICP備17016276號-1