algorithm-chapter--資料下載頁
2025-07-24 09:08本頁面
【正文】 分析 給定兩個方陣 A 和 B，根據(jù)矩陣乘法定義計算它們之乘積。 算法 MatrixMultiplication (A[0...n1][0...n1], B[0...n1][0...n1]) for i←0 to n1 do // 行循環(huán) for j←0 to n1 do // 列循環(huán) M[ i ][ j ]← // 積矩陣初始化 for k←0 to n1 do // 用變量 k 表示變化的腳標 M[ i ][ j ]←M[ i ][ j ] + A[ i ][ k ] * B[ k ][ j ] return M 02011,1nnjjiji i ijBBMA A AB???? ?????? ?????? ? ?????? ?????? ???? ????如果是非方陣，只需改變行列循環(huán)變量的范圍即可。本例均為 n1 輸入規(guī)模： 方陣的階 n 。非方陣：參與運算的元素個數(shù)。 基本操作： 最內(nèi)層循環(huán)有三種操作：乘法、加法、賦值。每次循環(huán)時， 每種操作均被執(zhí)行一次，所以任選一種作為基本操作均可，因它們的 執(zhí)行次數(shù)相同?？紤]操作的時間耗費：大多數(shù)計算機的乘法比加法更 費時，算術運算比賦值操作更費時。所以，本例選乘法為基本操作。 效率類別： 本例基本操作數(shù)只與輸入規(guī)模有關，與輸入元素分布無關， 不用分析最佳、最差和平均效率。 建立增長函數(shù) C(n) ： 1 1 1 1 1 10 0 0 0 0 0112 3120030( ) 111()n n n n n ni j i j i jnnkniinCnnnnnn? ? ? ? ? ?? ? ? ? ??? ???????? ? ? ????? ? ? ??? ? ? ? ? ????遞歸算法的數(shù)學分析 ?例：對于任意非負整數(shù) n，計算 F(n)=n!的值。 F(n)= n(n1)! , n1 1 , n=1 1 ,n=0 算法 F(n) //遞歸計算 n! //輸入：非負整數(shù) n //輸出： n!的值 if n=0 retuen 1 else return F(n1)*n M(n)= M(n1)+1 , n≥1 0 ,n=0 M(n)=M(n1)+1 =[M(n2)+1]+1=M(n2)+2 =[M(n3)+1]+2=M(n3)+3 …… =[M(nn)+1]+n1=n f u n (5 ) d 1 :f u n (4 ) d 2 :f u n (3 ) d 3 :f u n (2 ) d 4 :f u n (1 ) 返回 1 f u n (2 )=2 f u n (3 )=6 f u n (4 )=2 4 f u n (5 )=1 2 0 求解 5!的過程如下： 分析遞歸算法效率的通用方案 ?決定用哪個參數(shù)作為輸入規(guī)模的度量 ?找出算法的基本操作 ?檢查對相同規(guī)模的輸入，基本操作的執(zhí)行次數(shù)是否相同，如果不同，必須對最差、平均及最優(yōu)效率單獨研究 ?建立一個遞推關系式及相應的初始條件 ?求解這個遞歸關系式，或者至少確定解的增長次數(shù) 漢諾塔 M(n)= 2M(n1)+1 , n1 1 ,n=1 M(n)=2n1 我們應該謹慎使用遞歸算法，因為他們的簡潔可能會掩蓋他們的低效率。 Hanoi(n,a,b,c) Hanoi(n1,a,c,b)； move(n,a,c)； Hanoi(n1,b,a,c) n=4的情形 斐波那契數(shù)列 F(n)= F(n1)+F(n2) , n1 1 , n=1 0 ,n=0 0,1,1,2,3,5,8,13,21,34,…… 斐波那契數(shù)列的遞歸調(diào)用樹 : 算法的經(jīng)驗分析 ?對算法效率做經(jīng)驗分析的通用方案 ?了解試驗的目的 ?決定用來度量效率的量度 M和度量單位（單位時間內(nèi)的操作次數(shù)） ?決定輸入樣本的特性 ?為實驗準備算法的程序?qū)崿F(xiàn) ?生成輸入樣本 ?對輸入樣本進行計算，并記錄觀察到的實驗數(shù)據(jù) ?分析獲得的實驗數(shù)據(jù) 算法可視法 ?通過使用圖形來傳達關于算法的一些有用信息。 ?算法可視法的種類： ?靜態(tài)算法可視法 ?動態(tài)算法可視法 (算法動畫 , Algorithm Animation) 靜態(tài)算法可視法 靜態(tài)算法可視法 動態(tài)算法可視法 小結 ?算法效率包括時間效率和空間效率。 ?時間效率主要用它的輸入規(guī)模的函數(shù)來度量，該函數(shù)計算算法基本操作的執(zhí)行次數(shù)。 ?最差、最優(yōu)與平均效率 ?增長次數(shù) ?符號 O， Ω， Θ ?非遞歸算法和遞歸算法的效率分析 ?遞歸算法簡潔性可能會掩蓋它的低效率 ?算法的經(jīng)驗分析是針對一個輸入樣本，運行算法的一個程序?qū)崿F(xiàn)，然后分析觀測到的數(shù)據(jù)。
規(guī)章制度相關推薦
鄂ICP備17016276號-1