清華大學(xué)數(shù)據(jù)結(jié)構(gòu)(編輯修改稿)
2025-08-31 17:52 本頁面
【文章內(nèi)容簡介】 ? 通過 繼承 共享其父類的公共的和保護(hù)性的屬性和操作； ? 同一類的不同實(shí)例有不同的屬性值。 31 算法定義 ? 定義： 一個(gè)有窮的指令集 ，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列 ? 特性： ? 輸入 有 0個(gè)或多個(gè)輸入 ? 輸出 有一個(gè)或多個(gè)輸出 (處理結(jié)果 ) ? 確定性 每步定義都是確切無歧義的 ? 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束 ? 能行性 每一步運(yùn)算應(yīng)足夠基本 32 幾點(diǎn)說明 ? 注意算法與 計(jì)算方法 的區(qū)別 具有算法的其它特征 , 但不具有有窮性的特性 計(jì)算方法可以只保證理論上收斂； ? 算法與程序的區(qū)別 程序可以處于無休止的“等待”循環(huán)中； 算法描述可以有多種形式，如偽碼、框圖、表格、圖形等 33 ? 事例學(xué)習(xí)： 選擇排序 問題 ? 明確問題： 排序后關(guān)鍵字呈遞增 (非遞減 )排列 ? 解決方案： 逐個(gè)選擇當(dāng)前的最小元素 ? 算法框架： for (int i = 0。 i n1。 i++) { //n1趟 //從 a[i]檢查到 a[n1]。 //若最小元素為 a[k], 則將 a[i]與 a[k]交換 。 } ? 細(xì)化程序： 程序 SelectSort 算法設(shè)計(jì) 自頂向下，逐步求精 34 void selectSort ( int a[ ], const int n ) { //對 n個(gè)元素 a[0],a[1],…,a[n 1]按遞增順序排序 for (int i = 0。 i n1。 i++) { int k = i。 //從 a[i]查到 a[n1], 找最小元素 其位置 在 k for (int j = i+1。 j n。 j++) if (a[j] a[k]) k = j。 int temp = a[i]。 a[i] = a[k]。 a[k] = temp。 } } //有改進(jìn)余地 (何時(shí)必須交換 ) 35 算法簡單性能分析與度量 ? 算法的性能標(biāo)準(zhǔn) ? 算法的后期測試 ? 算法的事前估計(jì) 36 算法的性能標(biāo)準(zhǔn) ? 正確性 (Correctness ) 算法應(yīng)正確執(zhí)行預(yù)定的功能和性能要求。 ? 可讀性 (Readability) 算法應(yīng)該容易閱讀。以有利于閱讀者對程序的理解。 ? 效率 (Efficiency) 效率指的是算法執(zhí)行的時(shí)間和空間利用率。通常這兩者與問題的規(guī)模有關(guān)。 ? 健壯性 (Robustness) 算法應(yīng)具有容錯(cuò)處理的功能。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出反應(yīng)，而不應(yīng)產(chǎn)生莫名其妙的輸出結(jié)果。 37 算法的后期測試 ? 對一個(gè)算法要作出全面的分析大致可分成兩個(gè)階段進(jìn)行，即 事前分析 和 事后測試 ? 事前分析 要求事前求出該算法的一個(gè)時(shí)間界限函數(shù)。 ? 事后測試 則要求在算法執(zhí)行后通過算法執(zhí)行的時(shí)間和實(shí)際占用空間的統(tǒng)計(jì)資料來分析。 ? 事后分析要求在算法中的某些部位插裝時(shí)間函數(shù) time ( )， 測定算法完成某一功能所花費(fèi)的時(shí)間。 38 例如，考察順序搜索 (Sequenial Search)算法 int seqsearch ( int a[ ], int n, int x ) { //在 a[0],…,a[n 1]中搜索與給定值 x 相等的元 //素。成功時(shí)函數(shù)返回其位置，失敗返回 1。 int i = 0。 while (a[i] != x amp。amp。 i n) i++。 if ( i == n ) return 1。 return i。 } //思考如何改進(jìn) 39 實(shí)用的 插裝 clock( ) 的計(jì)時(shí)程序 clock_t start, stop。 //以毫秒 ms為單位 start = clock()。 int k = seqsearch (a, n, x)。 //統(tǒng)計(jì)該函數(shù)的執(zhí)行時(shí)間 stop = clock()。 double runTime = stop start。 cout n runTime endl。 算法運(yùn)行時(shí)間要受 輸入規(guī)模、利用編譯程序生成的目標(biāo)代碼的質(zhì)量、計(jì)算機(jī)程序指令系統(tǒng)的 性能 和速度等 因素 制約。 40 插裝 time( ) 的計(jì)時(shí)程序 time_t start, stop。 //以秒為單位 time(amp。start)。 int k = seqsearch (a, n, x)。 time(amp。stop)。 double runTime = stop start。 cout n runTime endl。 算法運(yùn)行時(shí)間要受 輸入規(guī)模、利用編譯程序生成的目標(biāo)代碼的質(zhì)量、計(jì)算機(jī)程序指令系統(tǒng)的 性能 和速度等 因素 制約。 41 算法的事前估計(jì) ? 算法的事前估計(jì)主要包括時(shí)間復(fù)雜性和空間復(fù)雜性的分析： ? 問題的規(guī)模： 如：矩陣的階數(shù)、圖的頂點(diǎn)個(gè)數(shù)、待排序序列的元素個(gè)數(shù)等。 ? 時(shí)間復(fù)雜性 ：算法所需時(shí)間和問題規(guī)模的函數(shù)，記為 T(n)。 當(dāng) n?? 時(shí)的時(shí)間復(fù)雜性，稱為 漸進(jìn)時(shí)間復(fù)雜性 。 ? 空間復(fù)雜性 ：算法所需空間和問題規(guī)模的函數(shù)。記為 S(n)。 當(dāng) n?? 時(shí)的時(shí)間復(fù)雜性，稱為 漸進(jìn)空間復(fù)雜性 。 42 空間復(fù)雜度度量 ? 存儲(chǔ)空間的固定部分 程序指令代碼的空間，常數(shù)、簡單變量、定長成分 (如數(shù)組元素、結(jié)構(gòu)成分、對象的數(shù)據(jù)成員等 )變量所占空間。 ? 可變部分 尺寸與實(shí)例特性有關(guān)的成分變量所占空間、引用變量所占空間、遞歸棧所用空間、通過new和 delete命令動(dòng)態(tài)使用的空間。 43 時(shí)間復(fù)雜度度量 ? 編譯時(shí)間 ? 運(yùn)行時(shí)間 ? 程序步 ? 語法上或語義上有意義的一段指令
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1