[計算機軟件及應用]數(shù)據(jù)結構第1章緒論(編輯修改稿)
2024-11-15 04:11 本頁面
【文章內(nèi)容簡介】 // 基本操作的實現(xiàn) void add( plex z1, plex z2, plex amp。sum ) { // 以 sum 返回兩個復數(shù) z1, z2 的和 = + 。 = + 。 } { 其它省略 …… } 23 算法和算法的衡量 一 . 算法 算法 :算法是對 特定問題 求解步驟 的一種描述 , 是指令的 有限序列 ，其中每一條指令表示一個或多個操作。 一個算法必須滿足以下五個重要 特性 ： 1．有窮性 2．確定性 3．可行性 4．有輸入 5．有輸出 24 1．有窮性 : 對于任意一組合法輸入值，在執(zhí)行 有窮步驟 之后一定能結束，且每一步驟都能在 有限時間內(nèi)完成。 2．確定性 : 對于 每種情況 下所應執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑。 3．可行性 : 算法中描述的操作都是可以通過 已經(jīng)實現(xiàn) 的 基本運算 執(zhí)行有限次來實現(xiàn)。 25 4．有輸入： 零個或多個的輸入。 作為算法加工對象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法之中。 5．有輸出： 一個或多個的輸出。 它是一組與 “ 輸入 ” 有確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能。 26 例 :試說明下列 算法過程 是否是一個算法： (1)開始 (2)n=0。 (3)n=n+1； (4)重復 (3)； (5)結束 。 有窮性？ 不是一個算法！ 27 二 . 算法設計的原則 設計算法時，通常應考慮達到以下目標： 1．正確性 2. 可讀性 3．健壯性 4．高效率與低存儲量需求 28 1．正確性 ⑴ 算法應當滿足以特定的“ 規(guī)格說明 ”方式給出的需求 。 ⑵ 對算法是否“正確”的理解可以有以下四個層次： a．程序中不含 語法錯誤 ； b．程序對于 幾組輸入數(shù)據(jù) 能夠得出滿足要求的結果； c． 程序對于 精心選擇的、典型、苛刻且?guī)в械箅y性的 幾組輸入數(shù)據(jù)能夠得出滿足要求的結果； d．程序對于 一切合法的輸入數(shù)據(jù) 都能得出滿足要求的結果； √ 通常以第 c 層意義的正確性作為衡量標準。 29 2. 可讀性 ?算法主要是為了人的閱讀與交流，其次才是為計算機執(zhí)行，因此算法應該 易于人的理解 ； ?另一方面，難讀的程序易于 隱藏較多錯誤 而難以調(diào)試。 3．健壯性 ?當輸入的 數(shù)據(jù)非法 時，算法應當恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是產(chǎn)生 莫名奇妙的輸出結果 ?處理出錯的方法不應是中斷程序的執(zhí)行，而應是返回一個 表示錯誤或錯誤性質(zhì)的值 ，以便進行處理 30 4．高效率與低存儲量需求 通常，效率指的是算法 執(zhí)行時間 ；存儲量指的是算法執(zhí)行過程中所需的 最大存儲空間 ，兩者都與問題的規(guī)模有關。 31 ? 算法與程序的區(qū)別 – 算法 是解決問題的一種方法或一個過程，考慮如何將輸入轉換成輸出，一個問題可以有 多個算法。 – 程序 是用某種程序設計語言對 算法的具體實現(xiàn)。 ? 主要區(qū)別： 有窮性、正確性和描述方法 – 程序可以是 無窮 的，例如 OS，算法是 有窮 的； – 程序可以是 錯誤 的，而算法必須是 正確 的； – 程序是用 程序設計語言描述 的，在機器上可以執(zhí)行，算法還可以用 自然語言、框圖、高級程序語言 等方式描述。 32 三 . 算法效率的衡量方法和準則 1. 對一個算法要作出全面的分析衡量，可分別使用兩種方法： 事后統(tǒng)計和事前分析 ? 事后統(tǒng)計 缺點： 1．必須執(zhí)行程序 2．其它因素掩蓋算法本質(zhì) 33 和算法執(zhí)行時間相關的 因素 ： ⑴ 算法選用的策略 ⑵ 問題的規(guī)模 ⑶ 編寫程序的語言 ⑷ 編譯程序產(chǎn)生的機器代碼的質(zhì)量 ⑸ 計算機執(zhí)行指令的速度 ?事前分析 與計算機硬件、軟件有關 34 “ 運行工作量 ” 通常是 隨 問題規(guī)模
教學課件相關推薦
鄂ICP備17016276號-1