1算法(25h)-wenkub.com
2024-07-31 06:47 本頁面
【正文】 通?？偸窃谧顗牡那闆r下分析算法的工作量 。 即從數(shù)組的第一個元素開始 ，逐個與被查值 x進行比較 。常見的時間復(fù)雜度有： O(1)， O(logn)， O(n)， O(n2 )， O(2n ) 常數(shù)階 對數(shù)階 線性階 平方階 指數(shù)階 空間復(fù)雜度 指算法在計算機上運行所占用的存儲空間的大小。 例： n皇后問題（ n=4） (參考教材 P9) 算法的復(fù)雜度分析 算法評價的標(biāo)準(zhǔn)： 時間復(fù)雜度 和 空間復(fù)雜度 。 2. 一種有效的方法是“試”。 ? 最后判斷減半后的區(qū)間長度是否已經(jīng)很小 。 利用二分法求該方程在區(qū)間 [a,b]上的一個實根 。 工程上常用的分治法是減半遞推技術(shù) 。 ??????????????2221121122211211bbbbBaaaaA??????????????????2222122121221121221212112112111122211211babababababababaccccC其乘積矩陣 C＝ AB為： ????????????????????????????))(())(()()()()())((2221221271211112162212115112122422121131122212221122111bbaaxbbaaxbaaxbbaxbbaxbaaxbbaax對于低階的矩陣相乘問題，如二階矩陣相乘，減少乘法次數(shù)是有可能的。遞歸則是從需求的函數(shù)本身出發(fā)，逐次上溯調(diào)用其本身求解過程，直到遞歸的出口，然后再從里向外倒推回來，得到最終的值。如果算法 P調(diào)用另一個算法 Q，而算法 Q又調(diào)用算法 P，則稱為間接遞歸調(diào)用。 如果一個過程直接或間接地調(diào)用它自身 ， 則稱該過程是遞歸的 ， 遞歸過程必須有一個遞歸終止條件 ，即存在 “ 遞歸出口 ” 。 遞歸法舉例說明 例： 編寫一個過程，對于輸入的參數(shù) n，依次打印輸 出自然數(shù) 1到 n。但在用新遞推算法遞推過程中，每遞推計算一次， 后一個計算值的誤差是前一個計算值誤差的 1/5，因此，當(dāng)計算到 I20時，其誤差是初值 I30誤差的 1/510 。 這個關(guān)系就可以得到如下遞推公式 遞推法例題分析 ? ?????? 100 1 8 2 3 2 )5/6l n (5ln6ln51 dxxI?????????? 20,2,1,511 8 2 3 2 10?nInIInn? 相鄰兩個積分之間除了具有遞推關(guān)系式 : nII nn151 ?? ?10 ??? nn II以外，還滿足下列不等式 因而， I20 應(yīng)比 I0小。但由于在歸納的過程中不可能對所有的情況進行列舉，因此，最后由歸納得到的結(jié)論還只是一種猜測，還需要對這種猜測加以必要的證明 。 if (3*i+2*j+*k==) coutsetw(5)isetw(5)jsetw(5)kednl。i=33。 ? 最后 ， 考慮到買的總雞數(shù)為 100， 而由第一層循環(huán)已確定買 I只母雞 ， 由第二層循環(huán)已確定買 J只公雞 ， 因此 ， 買小雞的數(shù)量只能是 K=100IJ， 即第三層循環(huán)已經(jīng)沒有必要了 。 } 總循環(huán)次數(shù)為 1013＝ 1030301 ? 首先 ， 考慮到母雞為 3元一只 ， 因此 ， 母雞最多只能買 33以 ，即算法中的外循環(huán)沒有必要從 0到 100． 而只需要從 0到 33就可以了 。 if(
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1