數(shù)據(jù)結(jié)構(gòu)選講datastructure(存儲版)
【正文】 loat C[n][n]) { int i,j,k。k++) // ④ C[i][j]=A[i][k]*B[k][j] // ⑤ } } 1232)( 23 ???? nnnnT2020/11/4 40 一般情況下，對步進(jìn)循環(huán)語句只考慮循環(huán)體語句的執(zhí)行次數(shù)，而忽略該語句中部長加一、終值判別、循環(huán)轉(zhuǎn)移等成份。i=n。i++) for (j=1。 j = temp。 此問題不僅與規(guī)模 n 有關(guān)，而且與數(shù)組 A中各元素的取值有關(guān)。A[i]!=k)) j。 例： temp = i。 for (i=1。k++) x++。 // ③ for( k=0。 ))(()( nfOnT ?2020/11/4 37 算法運行所需要的時間與兩個因素有關(guān)： 問題實例的大小 （ 如 1000個數(shù)的排序 ） ； 實例的具體情況 （如 1000個數(shù)的排列情況） 2020/11/4 38 算法分析 假定每條語句的執(zhí)行時間為單位時間 。因此，對反復(fù)運行的算法，首先考慮的是高效性，對偶爾運行的算法，則需突出算法易理解和易編程（以排序為例 － 冒泡排序和快速排序）。 } ? 細(xì)化程序： 程序 SelectSort 算法設(shè)計 自頂向下，逐步求精 性能分析與度量 ?算法的性能標(biāo)準(zhǔn) ?算法的后期測試 ?算法的事前估計 2020/11/4 31 分析評價算法時應(yīng)考慮的 因素： 正確性 在給定有效的輸入數(shù)據(jù)后 ， 算法經(jīng)過有窮時間的計算能給出正確的答案 。 避免使用轉(zhuǎn)向語句 避免使用預(yù)處理 避免函數(shù)返回值隱含說明 算法設(shè)計目標(biāo)和算法效率度量 ?定義： 一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列 ?特性： – 輸入 有 0個或多個輸入 – 輸出 有一個或多個輸出 (處理結(jié)果 ) – 確定性 每步定義都是確切、無歧義的 – 有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束 – 有效性 每一條運算應(yīng)足夠基本 算法的描述 :c++,c,PASCAL等語言 2020/11/4 28 算法有這樣一些 特點： 有窮性： 要求序列中的指令是有限的；每條指令的執(zhí)行包含有限的工作量；整個指令序列的執(zhí)行在有限的時間內(nèi)結(jié)束 。 2020/11/4 25 C語言的數(shù)據(jù)類型 基本數(shù)據(jù)類型 ?int short。 ?在解決問題時可能遇到的典型的邏輯結(jié)構(gòu)（數(shù)據(jù)結(jié)構(gòu)） ?邏輯結(jié)構(gòu)的存儲映象（存儲實現(xiàn)） ?數(shù)據(jù)結(jié)構(gòu)的相關(guān)操作及其實現(xiàn)。 – 數(shù)值性數(shù)據(jù) – 非數(shù)值性數(shù)據(jù) ? 數(shù)據(jù)對象： 數(shù)據(jù)的子集。 ? 數(shù)據(jù)結(jié)構(gòu)： 由某一數(shù)據(jù)對象及該對象中所有數(shù)據(jù)成員之間的關(guān)系組成。好的 DS通常對應(yīng)于好的（高效的）算法。 double。 例如：被零除的計算動作是不能被有效執(zhí)行的 。 此外還需考慮： 算法易于理解 ， 易于編程 （ 在計算機(jī)上實現(xiàn) ） ， 易于調(diào)試 。 我們假定 ， 每條語句一次執(zhí)行的時間都是相同的， 為單位時間 。 for(i=0。因此，當(dāng)有若干個循環(huán)語句時，算法的時間
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1