數(shù)據(jù)結(jié)構(gòu)選講datastructure-資料下載頁
2025-09-19 21:45本頁面
【導(dǎo)讀】嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).北京：清華大學(xué)出版社，數(shù)據(jù)結(jié)構(gòu)的基本概念。數(shù)據(jù)類型和抽象數(shù)據(jù)類型。用C語言描述算法的注意事項。算法設(shè)計目標和算法效率度量。算機程序識別和處理的符號的集合。具有相同性質(zhì)的數(shù)據(jù)。合及在這個集合上的一組操作。所有數(shù)據(jù)成員之間的關(guān)系組成。的視圖，是面向?qū)ο蟮?。體實現(xiàn)的視圖，是面向計算機的。DS，則稱它為好的DS。好的DS通常對應(yīng)于好。這是由計算機的計算能力決定的，因為。此可以利用樹設(shè)計出許多非常高效的算法。編程中最重要和最有用的一種數(shù)據(jù)結(jié)構(gòu)。
【正文】 // ③ for( k=0。kn。k++) // ④ C[i][j]=A[i][k]*B[k][j] // ⑤ } } 1232)( 23 ???? nnnnT2020/11/4 40 一般情況下，對步進循環(huán)語句只考慮循環(huán)體語句的執(zhí)行次數(shù)，而忽略該語句中部長加一、終值判別、循環(huán)轉(zhuǎn)移等成份。因此，當有若干個循環(huán)語句時，算法的時間復(fù)雜度是由嵌套層數(shù)最多的循環(huán)語句中最內(nèi)層語句的頻度所決定的。 2020/11/4 41 例： x=0。y=0。 for (k=1。k=n。k++) x++。 for (i=1。i=n。i++) for (j=1。j=n。j++) //n*n y++。 一般情況下，對步進循環(huán)語句只需考慮循環(huán)體中語句的執(zhí)行次數(shù)，而忽略循環(huán)體中步長加 終值判斷、控制轉(zhuǎn)移等成分。 2020/11/4 42 例： x=1。 for (i=1。i=n。i++) for (j=1。j=i。j++) for (k=1。k=j。k++) x++。 2/]2/)1(6/)12)(1([2/)1(1 1 11 1 1???????? ? ? ?? ? ?? ? ?? ? ?nnnnniijiniijniniijjk)()6/()( 33 nOnOnT ??? ?2020/11/4 43 選擇執(zhí)行的成分，如 if 語句的執(zhí)行時間，決定于then 子句、 else 子句耗時較多的部分 如果算法的執(zhí)行時間是一個與問題規(guī)模 n無關(guān)的常數(shù)，則算法的時間復(fù)雜度為常數(shù)階，記作 T(n)=O(1)。 例： temp = i。 i = j。 j = temp。 2020/11/4 44 很多算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，而且還與它所處理的數(shù)據(jù)集的狀態(tài)有關(guān)。通常是根據(jù)數(shù)據(jù)集中可能出現(xiàn)的最壞情況估計出算法的最壞時間復(fù)雜度。 2020/11/4 45 例： i=n1。 while ((i=0)amp。amp。A[i]!=k)) j。 return i。 此問題不僅與規(guī)模 n 有關(guān)，而且與數(shù)組 A中各元素的取值有關(guān)。 例： fact(n) { if (n = 1) return 1。 else return (n*fact(n1))。 } 設(shè) fact 的運行時間函數(shù)為 T（ n）， 則有 )1()1()( OnTnT ???)()1()1()1()1()2()1(2)1()1()(nOOnTOnnTOnTOnT????????????????2020/11/4 48 常數(shù)階 對數(shù)階 線性階 線性對數(shù)階 平方階 立方階 ……… K次方階 指數(shù)階 )1(O常見的時間復(fù)雜度，按數(shù)量級遞增排序： )( lo g 2 nO)(nO)lo g( 2 nnO)( 2nO)( 3nO)( knO)2( nO算法的后期測試 在算法中的某些部位插裝時間函數(shù) time ( ) 測定算法完成某一功能所花費的時間
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1