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