algorithm-chapter-(存儲(chǔ)版)
【正文】 數(shù) (2n)、階乘 (n!) 關(guān)于漸進(jìn)時(shí)間效率： 注 1 對(duì)規(guī)模較小的問(wèn)題 ,決定算法工作效率的可能是算法的簡(jiǎn)單性而不是算法執(zhí)行的時(shí)間。 ?常用求和公式（更多：教材附錄） 12211111 2 1001()1 1 1 1 1111 2 ( 1 ) ( )22112111 ( 1 ) 。 基本操作： 最內(nèi)層循環(huán)有三種操作：乘法、加法、賦值。 ?算法可視法的種類： ?靜態(tài)算法可視法 ?動(dòng)態(tài)算法可視法 (算法動(dòng)畫 , Algorithm Animation) 靜態(tài)算法可視法 靜態(tài)算法可視法 動(dòng)態(tài)算法可視法 小結(jié) ?算法效率包括時(shí)間效率和空間效率。 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 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!的過(guò)程如下： 分析遞歸算法效率的通用方案 ?決定用哪個(gè)參數(shù)作為輸入規(guī)模的度量 ?找出算法的基本操作 ?檢查對(duì)相同規(guī)模的輸入，基本操作的執(zhí)行次數(shù)是否相同，如果不同，必須對(duì)最差、平均及最優(yōu)效率單獨(dú)研究 ?建立一個(gè)遞推關(guān)系式及相應(yīng)的初始條件 ?求解這個(gè)遞歸關(guān)系式，或者至少確定解的增長(zhǎng)次數(shù) 漢諾塔 M(n)= 2M(n1)+1 , n1 1 ,n=1 M(n)=2n1 我們應(yīng)該謹(jǐn)慎使用遞歸算法，因?yàn)樗麄兊暮?jiǎn)潔可能會(huì)掩蓋他們的低效率。本例均為 n1 輸入規(guī)模： 方陣的階 n 。 4. 建立一個(gè)算法基本操作執(zhí)行次數(shù)的求和表達(dá)式。 例： 數(shù)組元素的查找算法（先排序后查找） 1. 對(duì)數(shù)組元素排序 2. 2. 順序查找有序數(shù)組 T1 (n) = (n1) ∈ Θ(n2) T2(n) = n ∈ Θ(n) 算法的整體效率： T(n) ∈ Θ(n2) 利用極限比較增長(zhǎng)次數(shù) 前兩種情況意味著 t(n) ∈ O(g(n)) 后兩種情況意味著 t(n) ∈ Ω(g(n)) 第二種情況意味著 t(n) ∈ Θ(g(n)) 【 例 】 比較 (n1) 和 n2 的增長(zhǎng)率 或證明： (n1)∈ Θ(n2) 22220 . 5 ( 1 ) 1 1 1 1lim lim lim( 1 )2 2 20 . 5 ( 1 ) ( )n n nn n n nn n nn n n? ? ? ? ? ???? ? ? ?? ? ? ?【 例 2】 2l o g nn比 較 和 的 增 長(zhǎng) 次 數(shù)2222log ( log ) 39。 后續(xù)章節(jié)中，除特別說(shuō)明外，都采用最差時(shí)間效率。以后討論平均效率時(shí)都引用已知的 推導(dǎo)結(jié)果。 實(shí)際中考慮該最差效率是否可以接受。 【 分析 】 —— 時(shí)間效率與查找鍵在表中的位置有關(guān)。因?yàn)? t 減少 10 倍， C(n) 不變?？紤]輸入規(guī)模的選擇？ 輸入規(guī)模：數(shù)值的 二進(jìn)制位數(shù)。 Time is Important 不是所有能計(jì)算的都有價(jià)值，不是所有有價(jià)值的都能被計(jì)算 ——阿爾伯特 .愛因斯坦 算法分析 ?需解決的問(wèn)題 ?度量一個(gè)算法的時(shí)間效率 (時(shí)間費(fèi)用 ) ?度量一個(gè)算法的空間效率 (空間費(fèi)用 ) ?優(yōu)化算法 ?最小化一個(gè)算法的時(shí)間效率或空間效率 ?途徑 ?理論分析 ?經(jīng)驗(yàn)分析 分析框架 —— 輸入規(guī)模度量 ?輸入規(guī)模度量 ?算法的時(shí)間效率和空間效率都用輸入規(guī)模的函數(shù)進(jìn)行度量。 ?選擇輸入規(guī)模的合適量度，要受到所討論算法的操作細(xì)節(jié)影響。 一個(gè)算法有許多操作，決定算法耗時(shí)的是那些 最費(fèi)時(shí) 的操作， 因此，只需統(tǒng)計(jì)這些最費(fèi)時(shí)的操作稱為 基本操作 。 ?最優(yōu)效率是指在輸入規(guī)模為 n是，算法在最優(yōu)情況下的效率。 最差時(shí)間效率 —— 若鍵位于表中，比較次數(shù)不定。 若算法的最優(yōu)時(shí)間效率不能滿足實(shí)際需要，立即拋棄該算法。 直接分析法 統(tǒng)計(jì)或者假設(shè)隨機(jī)輸入的概率分布，以推導(dǎo)基本操作的平均次數(shù)。 于是， T(n) 可表示為： T*(n) = 3 , c 0 【 定義 】 T*(n) —— 算法的漸近時(shí)間復(fù)雜性（時(shí)間效率） 【 思考 】 兩個(gè)算法比較時(shí)，為什么常數(shù) c 不重要？ *( ) (
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1