2第二章算法效率分析基礎(chǔ)(編輯修改稿)
2025-03-28 04:03 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 入：實(shí)數(shù)數(shù)組 A[0..n1] //輸出： A中的最大元素 maxval ?A[0] for i ? 1 to n1 do if A[i] maxval maxval ? A[i] return maxval 考慮： 1. 循環(huán)中的操作有 比較 和 賦值 ，取哪一個(gè)作為基本操作？ 2. 輸入規(guī)模是多少？ 基本操作為：比較運(yùn)算 輸入規(guī)模就是數(shù)組長(zhǎng)度 n 算法的效率為： Analysis and Design of Computer Algorithms 169。 School of Computer Science and Technology, SWUST 16 分析非遞歸算法效率的通用方案 1. 決定用那些參數(shù)作為輸入規(guī)模的度量。 2. 找出算法的基本操作。 3. 檢查基本操作的執(zhí)行次數(shù)是否只依賴(lài)輸入規(guī)模。 4. 建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式。 5. 利用求和運(yùn)算的標(biāo)準(zhǔn)公式和法則來(lái)建立一個(gè)操作次數(shù)的閉合公式，或者至少確定它的增長(zhǎng)次數(shù)。 Analysis and Design of Computer Algorithms 169。 School of Computer Science and Technology, SWUST 17 Example 考慮下面算法的效率 ?Example 2 元素唯一性問(wèn)題 算法 UniqueElements(A[0..n1]) //驗(yàn)證給定數(shù)組的元素是否全部唯一 //輸入：實(shí)數(shù)數(shù)組 A[0..n1] //輸出：如果唯一，返回 True，否則 False for i?0 to n2 do for j?i+1 to n1 do if A[i]=A[j] return False return True ?Example 3 兩個(gè) n階方陣乘法 算法 MatrixMuti(A[0..n1,0..n1],B[0..n1,0..n1]) //根據(jù)定義計(jì)算兩個(gè) n階矩陣的乘積 //輸入：兩個(gè) n階矩陣 //輸出：矩陣 C=AB for i?0 to n1 do for j?0 to n1 do C[i,j] ? for k ? 0 to n1 do C[i,j] = C[i,j] + A[i,k] * B [k,j] return C Analysis and Design of Computer Algorithms 169。 School of Computer Science and Technology, SWUST 18 遞歸算法的數(shù)學(xué)分析 ?例：對(duì)于任意非負(fù)整數(shù) n，計(jì)算 F(n)=n!的值。 F(n)= n(n1)! , n1 1 , n=1 1 ,n=0 算法 F(n) //遞歸計(jì)算 n! //輸入：非負(fù)整數(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 Analysis and Design of Computer Algorithms 169。 School of Computer Science and Technology, SWUST 19 分析遞歸算法效率的通用方案 ?決定用哪個(gè)參數(shù)作為輸入規(guī)模的度量 ?找出算法的基本操作
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1