數據結構課件緒論-預覽頁
【正文】 之間的邏輯關系。 說明：四種存儲方法可結合起來對數據結構進 行存儲映像。 抽象數據類型 —— ADT ? 定義：是指基于一個邏輯類型的數據模型以及定義在該模型上的一組操作。 算法的重要特性 P13 (1) 有窮性 ：能執(zhí)行結束 (2) 確定性 ：對于相同的輸入執(zhí)行相同的路徑 (3) 0至多個輸入 (4) 1至多個輸出 (5) 有效性 (可行性 ) （用于描述算法的操作都是 足夠基本的） ? 問題：程序是不是算法？ ? 如操作系統(tǒng)，只要系統(tǒng)不遭破壞，它就永遠不會停止，即使沒有作業(yè)要處理，仍處于一個等待循環(huán)中，等待新作業(yè)的進入。 ? 一個算法總是建立在一定數據結構上的；反之，算法不確定，就無法決定如何構造數據。 姓名 選修 1 選修 2 選修 3 A B E C D C E F D F A B F 算法與數據結構關系舉例 ? 解決該問題，首先選擇一個合適的數據結構。 ? 答案： 1： A,C 2:B,D 3:E 4: F ? 解決問題的關鍵步驟是先選取合適的數據結構表示問題，才能寫出有效的算法。 s=0； } ++x 的頻度為 1 （ b） for (i=1。} ++x的頻度為 n （ c） for (j=1。++k) {++x。頻度統(tǒng)計法 表：時間復雜度和算法運行時間的關系 T(n) n O(logn) O(n) O(nlogn) O(n2 ) O(n3 ) O(n5 ) O(2n ) O(n!)) 20 20us 400us 8ms 771世紀 40 40 213 1600 64ms *1032世紀 60 60 354 3600 216ms 13min 366世紀 *1066世紀 結論 （ 1）當 f(n)為對數函數、冪函數、或它們的乘積時，算法的運行時間是可以接受的，稱這些算法是有效算法；當 f(n)為指數函數或階乘函數時，算法的運行時間是不可接受的，稱這些算法是無效
環(huán)評公示相關推薦
鄂ICP備17016276號-1