1算法(25h)(參考版)
2024-08-04 06:47本頁(yè)面
【正文】 2. 最優(yōu)算法是指在解決一個(gè)問(wèn)題時(shí) ， 如果在被研究的算法類中 ， 沒(méi)有一個(gè)算法比現(xiàn)有算法執(zhí)行更少的基本運(yùn)算 ， 則稱此算法是最優(yōu)的 。 ? 如果已知需要查找的 x有一半的機(jī)會(huì)在數(shù)組中 ，此時(shí) q＝ 1／ 2；則 A(n)=[(n+1)/4]+n/2≈3n/4 ?????????)1(1)1(/niqninqpinqqnnqinqtpnAniniii )1(2/)1()1()/()(111???????? ?????最壞情況分析 ? 在這個(gè)例子中，最壞情況發(fā)生在需要查找的 x是數(shù)組中的最后一個(gè)元素，或 x不在數(shù)組中的時(shí)候，此時(shí)顯然有： nnitnW i ????? }11|m a x {)(算法的最優(yōu)性 1. 衡量算法的好壞主要依據(jù)算法的復(fù)雜度 ， 特別是時(shí)間復(fù)雜度 。 基本運(yùn)算為 x與數(shù)組元素的比較 。 ? 它定義為： )}({m a x)( xtnWnDx ??例題 例：采用順序搜索法 ， 在長(zhǎng)度為 n的一維數(shù)組中查找值為 x的元素 。 （程序、輸入、額外輔助） 平均性態(tài) ? 所謂平均性態(tài)分析，是指用各種特定輸入下的基本運(yùn)算次數(shù)的 帶權(quán)平均值 來(lái)度量算法的工作量。用“ O（數(shù)量級(jí)）”來(lái)表示，稱為“階”。 時(shí)間復(fù)雜度 指在計(jì)算機(jī)上運(yùn)行該算法所花費(fèi)的時(shí)間。這種方法稱為回溯法。通過(guò)對(duì)問(wèn)題的分析，找出一個(gè)解決問(wèn)題的線索；然后沿著這個(gè)線索逐步試探。 } c＝ (a＋ b)/2； return(c) 基本思想 1. 在工程上，有些實(shí)際問(wèn)題卻 很難歸納 出一組簡(jiǎn)單的遞推公式或直觀的求解步驟，并且也不能進(jìn)行無(wú)限的列舉。 若 |ab|ε， 則過(guò)程結(jié)束 ， 取 （ a+b） /2為根的近似值；否則 ，則重復(fù)上述的減半過(guò)程 。 若 f(c)=0， 則說(shuō)明 c即為所求的根 ， 求解過(guò)程結(jié)束；如果 f(c) ≠0 ， 則根據(jù)以下原則將原區(qū)間減半： 若 f(a)f(c)0， 則取原區(qū)間的前半部分； 若 f(b)f(c)0 ， 則取原區(qū)間的后半部分 。 分析： ? 首先取 給 定區(qū)間的中點(diǎn) c=(a+b)/2。 例題 設(shè)方程 f(x)=0在區(qū)間 [a,b]上有實(shí)根 ， 且 f(a)與 f(b)異號(hào) 。 這個(gè)技術(shù)在快速算法的研究中有很重要的實(shí)用價(jià)值 。 ???????????????????62312242215312754111xxxxcxxcxxcxxxxc減半遞推技術(shù)舉例 根據(jù)以上分析 ， 假設(shè) ， 且 階矩陣相乘所需要的乘法次數(shù)為 M（ k） ， 則有 kn 2? kn 2?)0(7)2(7)1(7)( 2 MkMkMkM k?????? ?減半遞推技術(shù) 例題分析 o gl o g 2277)( nnkM nk ????因此有 減半遞推技術(shù) 總結(jié)： ? 對(duì)問(wèn)題分而治之 。令： 減半遞推技術(shù)舉例 乘積矩陣 C中的各元素可用以上 7個(gè)量的線性組合來(lái)表示： 上述方法計(jì)算兩個(gè) 二階矩陣相乘只需要 7次乘法就夠 了，比通常的方法減少了 1次乘法。那么兩個(gè)二階矩陣相乘需要作 8次乘法。一般說(shuō)來(lái)，一個(gè)遞推算法總可以轉(zhuǎn)換為一個(gè)遞歸算法。遞推是從已知的初始條件出發(fā)，逐次遞推出最后所求的值。 ? 遞歸過(guò)程能將一個(gè)復(fù)雜的問(wèn)題歸結(jié)為若干個(gè)較簡(jiǎn)單的問(wèn)題，然后將這些較簡(jiǎn)單的每一個(gè)問(wèn)題再歸結(jié)為更簡(jiǎn)單的問(wèn)題，這個(gè)過(guò)程可以一直做下去，直到最簡(jiǎn)單的問(wèn)題為止。如果一個(gè)算法 P顯式地調(diào)用自己則稱為直接遞歸，例如算法 。 無(wú)條件的遞歸是毫無(wú)意義的 。 PROC
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1