1算法(25h)-閱讀頁(yè)
2024-08-12 06:47本頁(yè)面
【正文】 ???????????2221121122211211bbbbBaaaaA??????????????????2222122121221121221212112112111122211211babababababababaccccC其乘積矩陣 C＝ AB為： ????????????????????????????))(())(()()()()())((2221221271211112162212115112122422121131122212221122111bbaaxbbaaxbaaxbbaxbbaxbaaxbbaax對(duì)于低階的矩陣相乘問(wèn)題，如二階矩陣相乘，減少乘法次數(shù)是有可能的。以此類(lèi)推，最后可以歸結(jié)為計(jì)算一階矩陣相乘的問(wèn)題，而一階矩陣相乘只需要一次乘法。 工程上常用的分治法是減半遞推技術(shù) 。 所謂 “ 減半 ” ， 是指將問(wèn)題的 規(guī)模減半 ， 而問(wèn)題的性質(zhì)不變 ， 所謂 “ 遞推 ” ， 是指 重復(fù) “ 減半 ” 的過(guò)程 。 利用二分法求該方程在區(qū)間 [a,b]上的一個(gè)實(shí)根 。 ? 然后判斷 f(c)是否為 0。 ? 最后判斷減半后的區(qū)間長(zhǎng)度是否已經(jīng)很小 。 double root(a， b， eps， f) double a,b ,exp,(*f)() f0＝ f(a) while(|a－ b|≥eps) DO { c＝ (a＋ b)/2； f1＝ (*f)(c) if (f1==0) { return c } if (f0*f1＞ 0) a＝ c else b＝ c。 2. 一種有效的方法是“試”。 3. 對(duì)于每一步試探，若試探成功，就得到問(wèn)題的解；若試探失敗，就逐步回退，換別的路線再進(jìn)行試探。 例： n皇后問(wèn)題（ n=4） (參考教材 P9) 算法的復(fù)雜度分析 算法評(píng)價(jià)的標(biāo)準(zhǔn)： 時(shí)間復(fù)雜度 和 空間復(fù)雜度 。常以基本運(yùn)算的重復(fù)次數(shù)來(lái)衡量。常見(jiàn)的時(shí)間復(fù)雜度有： O(1)， O(logn)， O(n)， O(n2 )， O(2n ) 常數(shù)階 對(duì)數(shù)階 線性階 平方階 指數(shù)階 空間復(fù)雜度 指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲(chǔ)空間的大小。 ? 設(shè) x是所有可能輸入中的某個(gè)特定輸入 ， p(x)是 x出現(xiàn)的概率 （ 即輸入為 x的概率 ） ， t(x)是算法在輸入為 x時(shí)所執(zhí)行的基本運(yùn)算次數(shù) ， 則算法的平均性態(tài)定義為： ???nDxxtxpnA )()()(最壞情況復(fù)雜性 ? 所謂 最壞情況分析 ，是指在規(guī)模為 n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。 即從數(shù)組的第一個(gè)元素開(kāi)始 ，逐個(gè)與被查值 x進(jìn)行比較 。 ? 平均性態(tài)分析 設(shè)被查項(xiàng) x在數(shù)組中的概率為 q ????????)1()1(ninniiti? 如果已知需要查找的 x一定在數(shù)組中 ， 此時(shí) q＝ 1，則 A(n)=（ n＋ l） ／ 2。 通?？偸窃谧顗牡那闆r下分析算法的工作量 。 總結(jié)： 算法的基本概念 算法的基本特征 算法的要素 算法描述語(yǔ)言 算法設(shè)計(jì)基本方法 算法復(fù)雜度分析 課堂練習(xí) ? ? 給定三個(gè)整數(shù) a,b,c 寫(xiě)出尋找其中數(shù)的算法，并分析平均和最壞情況下要作多少次比較？ 作業(yè) ? P12 ? .
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1