算法設(shè)計基本方法ppt課件(編輯修改稿)
2025-06-08 12:54 本頁面
【文章內(nèi)容簡介】 { int low,high,mid。 low=1。 high=n。 while (low=high){ mid = if(xA[mid]) high=mid1。 if(xA[mid]) low =mid+1。 else return mid。 } return 0。 } ? ?h ig h ) / 2( lo w ?注 ： 給定一個按非降次序排列的元素數(shù)組 A(1:n)， n≥1,判斷 x是否出現(xiàn)。 ?若是，返回當前角標 mid ?若非，返回 0，表示沒有找到 例：設(shè) A(1:9)=(15， 6， 0， 7， 9， 23， 54， 82， 101) 在 A中檢索 x=101， 14， 82。執(zhí)行軌跡見下表 1 表 1 運行軌跡示例 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ù) 特點：迅速縮小計算規(guī)模 適用范圍：工程計算，矩陣計算，數(shù)值計算中能夠迅速將問題分治的情況 算法設(shè)計基本方法（ 6） ? 回溯法 ? 通過對問題的分析，找出一個解決問題的線索，然后沿著這個線索逐步試探，對于每一步的試探，若試探成功，就得到問題的解，若試探失敗，就逐步回退，換別的路線再進行試探。 例：八皇后問題（教材 p15）迷宮問題 實際上是一種圖的深度優(yōu)先遍歷的方法 特點：算法效率高，直觀清楚 適用范圍：適用于解決 “ 是否存在 ” 或者 “ 有多少種可能 ” 問題 缺點：算法的復(fù)雜性與計算順序有關(guān) 算法分析 1. 分析算法的目的 在于：通過對算法的分析，在把算法變成程序?qū)嶋H運行前，就知道為完成一項任務(wù)所設(shè)計的算法的好壞，從而運行好的算法，改進差的算法，避免無益的人力和物力浪費。 算法分析是計算機領(lǐng)域的“古老”而“前沿”的課題。 算法分析 ? “好”的算法應(yīng)當達到以下指標 ? 正確性 (Correctness):算法應(yī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的元素。 算法 :即從數(shù)組的第一個元素開始，逐個與被查值 x進行比較。 基本運算 :x與數(shù)組元素的比較。 平均性態(tài)分析 : 最壞情況分析 : W(n)＝ max{ti | 1≤i≤n＋ 1}＝ n 如何進行算法分析？ 對算法進行全面分析，可分兩個階段進行： ?事前分析 ：求算法的一個 時間 /空間限界函數(shù) ，即通過對算 法的“理論”分析，得出關(guān)于算法 時間和空間特性 的特征函數(shù)（ Ο、 Ω） ——與計算機物理軟硬 件沒有直接關(guān)系。 ?事后測試 ：將算法編制成程序后實際放到計算機上運行， 收集其執(zhí)行時間和空間占用等統(tǒng)計資料，進行 分析判斷 ——直接與物理實現(xiàn)有關(guān)。 1）事前分析 ? 目的：試圖得出關(guān)于算法特性的一種形式描 述（限界函數(shù)），以“理論上”衡量算法的“好壞”。 ? 如何給出反映算法特性的描述 ？ 統(tǒng)計算法中各種運算的執(zhí)行情況，包括： ? 引用了哪些運算 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1