數(shù)據(jù)結(jié)構(gòu)第一章-在線瀏覽
2024-09-14 16:53本頁(yè)面
【正文】 ct Data Type， ADT） 描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具 ? 是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作 。 ADT 抽象數(shù)據(jù)類(lèi)型名 { 數(shù)據(jù)對(duì)象： 〈 數(shù)據(jù)對(duì)象的定義 〉 數(shù)據(jù)關(guān)系： 〈 數(shù)據(jù)關(guān)系的定義 〉 基本操作： 〈 基本操作的定義 〉 } ADT 抽象數(shù)據(jù)類(lèi)型名 抽象數(shù)據(jù)類(lèi)型 例如，抽象數(shù)據(jù)類(lèi)型復(fù)數(shù)的定義： ADT Complex { 數(shù)據(jù)對(duì)象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關(guān)系： R1＝ {e1,e2 | e1是復(fù)數(shù)的實(shí)數(shù)部分； e2 是復(fù)數(shù)的虛數(shù)部分 } 基本操作： AssignComplex( amp。 DestroyComplex( amp。 GetReal( Z, amp。 操作結(jié)果：用 realPart返回復(fù)數(shù) Z的實(shí)部值。ImagPart ) 初始條件：復(fù)數(shù)已存在。 Add( z1,z2, amp。 操作結(jié)果：用 sum返回兩個(gè)復(fù)數(shù) z1, z2 的和值。 ? 程序是算法的一種實(shí)現(xiàn)，計(jì)算機(jī)按照程序逐步執(zhí)行算法，實(shí)現(xiàn)對(duì)問(wèn)題的求解。并且在任何條件下，算法只有唯一的一條執(zhí)行路徑，相同的輸入只能得出相同的輸出。 ? 輸入 ? 零個(gè)或多個(gè)輸入。處理出錯(cuò)的方 法也不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回 一個(gè)表示錯(cuò)誤或錯(cuò)誤性質(zhì)的值，以便在更 高的抽象層次上進(jìn)行處理 高效率與低存儲(chǔ)量： 效率指的是算法執(zhí)行時(shí)間；存儲(chǔ)量指 的是算法執(zhí)行過(guò)程中所需的最大存儲(chǔ) 空間 ? 解決同一個(gè)問(wèn)題存在多種算法，如何評(píng)估各算法的好壞？或據(jù)此設(shè)計(jì)出更好的算法？ ? 運(yùn)行該算法所需要的計(jì)算機(jī)資源的多寡，所需越大復(fù)雜性越高 ? 最重要的資源：時(shí)間（處理器）和空間（存儲(chǔ)器） ? 評(píng)價(jià)一個(gè)算法優(yōu)劣的重要依據(jù)是看執(zhí)行該算法的程序需要占用多少機(jī)器資源： ? 程序所用算法運(yùn)行時(shí)所要花費(fèi)的時(shí)間代價(jià) ? 程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價(jià) 算法復(fù)雜度分析 算法復(fù)雜度分析 ? 算法的復(fù)雜度包含： 時(shí)間復(fù)雜度 空間復(fù)雜度 ? 主要考慮 時(shí)間復(fù)雜度 ? 設(shè)計(jì)算法的目標(biāo)和準(zhǔn)則：復(fù)雜性最低 算法復(fù)雜度分析 ? 和算法執(zhí)行時(shí)間相關(guān)的因素 ? 算法選用的策略 ? 問(wèn)題的規(guī)模 ? 編寫(xiě)程序的語(yǔ)言 ? 編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量 ? 計(jì)算機(jī)執(zhí)行指令的速度 算法復(fù)雜度分析 ? 問(wèn)題的輸入規(guī)模（ Input Size）依賴(lài)于所研究的問(wèn)題本身 ，輸入規(guī)模即為輸入項(xiàng)的個(gè)數(shù)，例如：排序和計(jì)算離散傅立葉變換（ DFT），輸入數(shù)組的元素個(gè)數(shù) n即為 input size 2. 還有一些問(wèn)題，輸入規(guī)模表示輸入數(shù)據(jù)的二進(jìn)制形式的 bit位數(shù)，例如：兩個(gè)整型數(shù)據(jù)的乘法 3. 有時(shí)，輸入規(guī)模用兩個(gè)數(shù)表示，例如輸入是一個(gè) 圖 所以，解決問(wèn)題之前先弄清 問(wèn)題的輸入規(guī)模 后面均將輸入規(guī)模抽象成 n，算法的運(yùn)行時(shí)間表示成 T(n),n的函數(shù) 算法復(fù)雜度分析 ? 最好運(yùn)行時(shí)間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最快情況的運(yùn)行時(shí)間。 運(yùn)行時(shí)間的上界 ? 平均運(yùn)行時(shí)間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，平均所需的運(yùn)行時(shí)間，通常指概率平均或期望值 ? 運(yùn)行時(shí)間 T(n)：主要操作的執(zhí)行次數(shù) ? 非遞歸算法： （ 1） for / while 循環(huán) 循環(huán)體內(nèi)運(yùn)行時(shí)間 *循環(huán)次數(shù)； （ 2）嵌套循環(huán) 循環(huán)體內(nèi)運(yùn)行時(shí)間 *所有循環(huán)次數(shù)； （ 3）順序語(yǔ)句 各語(yǔ)句運(yùn)行時(shí)間相加； （ 4） ifelse語(yǔ)句 if語(yǔ)句運(yùn)行時(shí)間和 else語(yǔ)句運(yùn)行時(shí)間的較大者。 算法分析舉例： InsertionSort InsertSort on the array A= 5,2,4,6,1,3 算法分析舉例： InsertionSort ? INSERTIONSORT(A) ? 1 for j← 2 to length[A] ? 2 do key ← A[j] ? 3
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1