jnqaaaalgorithm-chapter--wenkub.com
2025-07-21 13:01 本頁面
【正文】 ?最差、最優(yōu)與平均效率 ?增長(zhǎng)次數(shù) ?符號(hào) O， Ω， Θ ?非遞歸算法和遞歸算法的效率分析 ?遞歸算法簡(jiǎn)潔性可能會(huì)掩蓋它的低效率 ?算法的經(jīng)驗(yàn)分析是針對(duì)一個(gè)輸入樣本，運(yùn)行算法的一個(gè)程序?qū)崿F(xiàn)，然后分析觀測(cè)到的數(shù)據(jù)。 Engineering 26 靜態(tài)算法可視法 Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 23 Analysis and Design of Computer Algorithms Yunnan University School of Information Science amp。 Engineering 20 漢諾塔 M(n)= 2M(n1)+1 , n1 1 ,n=1 M(n)=2n1 我們應(yīng)該謹(jǐn)慎使用遞歸算法，因?yàn)樗麄兊暮?jiǎn)潔可能會(huì)掩蓋他們的低效率。 Engineering 17 Example 考慮下面算法的效率 ?Example 2 元素唯一性問題 算法 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 Yunnan University School of Information Science amp。 3. 檢查基本操作的執(zhí)行次數(shù)是否只依賴輸入規(guī)模。 Engineering 15 非遞歸算法的數(shù)學(xué)分析 ?Example 1：討論下面這個(gè)算法（從 n個(gè)元素中查找最大元素問題）的效率。 ?該定理表明： 當(dāng)算法由兩個(gè)連續(xù)執(zhí)行部分組成時(shí)，該算法的整體效率由具有較大增長(zhǎng)次數(shù)的那部分所決定。 Engineering 9 符號(hào) O ? 定義 1 對(duì)于足夠大的 n， t(n)的上界由 g(n)的常數(shù)倍來確定，即： ? 記為 t(n) ∈ O(g(n)) t(n) ≤ cg(n)， c為常數(shù) n ∈ O(n2) 100n+5 ∈ O(n2) n(n1)/2 ∈ O(n2) Anal
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1