世紀高等院校規(guī)劃教材數(shù)據結構c語言版-資料下載頁
2025-07-18 00:59本頁面
【正文】 022/8/15 26 為解決理解與執(zhí)行的矛盾 ， 常使用一種稱為偽碼 （ 類 ） 語言的描述方法來進行算法描述 。 類語言介于高級程序設計語言和自然語言之間 ， 它忽略高級程序設計語言中一些嚴格的語法規(guī)則與描述細節(jié) ， 因此它比程序設計語言更容易描述和被人理解 ， 而且比自然語言更接近程序設計語言 。它雖然不能直接執(zhí)行但很容易被轉換成高級語言 。 2022/8/15 27 算法設計的要求 要設計一個好的算法通常要考慮以下要求 。 ⑴ 正確 性 (Correctness)： 算法的執(zhí)行結果應當滿足預先規(guī)定的功能和性能要求 。 ⑵可讀 性 (Readability)： 算法應當思路清晰、層次分明、簡單明了、易讀 易懂。 以有利于閱讀者對程序的理解。 ⑶ 健壯性 (Robustness)： 算法應具有容錯處理 。 當輸入非法數(shù)據時 ， 算法應對其作出反應并適當處理 ， 不至引起嚴重后果 。 ⑷高效性和存儲量需求：效率指算法執(zhí)行的時間。對于解決同一問題的多個算法，執(zhí)行時間短的算法效率高。存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。 算法分析與評價 2022/8/15 28 算法效率的度量 1．時間復雜度 （ Time plexity） 一個算法的時間復雜度是指算法運行從開始到結束所需要的時間。 通常是所處理問題規(guī)模的一個函數(shù) T(n) ，常采用數(shù)量級的形式表示。記作： T(n)=O(f(n)) 稱 T(n)為算法的 (漸近 )時間復雜度。 2022/8/15 29 2． 空間復雜度 （ Space plexity） 一個算法的空間復雜度是指算法運行從開始到結束所需的存儲量 。 算法的存儲量指的是算法執(zhí)行過程中所需的最大存儲空間 。 算法執(zhí)行期間所需要的存儲量應該包括以下三部分： (1) 輸入數(shù)據所占空間； (2) 程序本身所占空間； (3) 輔 助變量所占空間 。 類似于算法的時間復雜度 ， 通常以算法的空間復雜度作為算法所需存儲空間的量度 。 定義： S(n)=O(g(n)) 稱 S(n)為算法的空間復雜度 。 2022/8/15 30 1． 數(shù)據結構研究的是數(shù)據的表示和數(shù)據之間的關系 。 從邏輯上講 ， 數(shù)據有集合 、 線性 、 樹和圖四種結構 。 從存儲結構上講 ，數(shù)據有順序結構 、 鏈接結構 、 索引結構和散列結構四種 。 理論上 ， 任一種數(shù)據邏輯結構都可以用任一種存儲結構來實現(xiàn) 。 2． 在集合結構中 ， 數(shù)據處于無序的 、 各自獨立的狀態(tài)；在線性結構中 ， 數(shù)據之間是 1對 1的關系；在樹結構中 ， 數(shù)據之間是 1對多的關系；在圖結構中 ， 數(shù)據之間是多對多的關系 。 3． 就存儲結構而言 ， 一個數(shù)組占有一片連續(xù)的存儲空間 ， 每個元素的物理存儲單元是按下標位置從 0開始連續(xù)編號的 ， 相鄰元素之間其存儲位置也相鄰 。 對于任一種數(shù)據的邏輯結構 ， 若能夠把元素之間的邏輯關系對應地轉換為數(shù)組下標位置之間的物理關系 ， 則就能夠利用數(shù)組來實現(xiàn)其順序存儲結構 。 本章小結 2022/8/15 31 4． 抽象數(shù)據類型是數(shù)據和對數(shù)據進行各種操作的集合體 。 這里所說的數(shù)據是廣義的 ， 是帶有結構的數(shù)據 ， 它可以具有任何邏輯結構和存儲結構 。 5． 算法的評價指標主要為正確性 、 健壯性 、 可讀性和有效性四個方面 。 有效性又包括時間復雜度 (性 )和空間復雜度 (性 )兩個方面 。 一個算法的時間和空間復雜度越好 ， 就越節(jié)省時間和空間 ， 則表明該算法越有效 。 6． 算法的時間復雜度和空間復雜度通常用數(shù)量級的形式表示出來。數(shù)量級的形式可分為常量級，對數(shù)級、線性級、平方級、立方級等多個級別。當數(shù)據處理量較大時，處于前面級別的算法比處于后面級別的算法更有效。
黨政相關相關推薦
鄂ICP備17016276號-1