algorithm-chapter-(文件)
【正文】 Ω和 Θ，該定理也成立。 例： 數(shù)組元素的查找算法（先排序后查找） 1. 對數(shù)組元素排序 2. 2. 順序查找有序數(shù)組 T1 (n) = (n1) ∈ Θ(n2) T2(n) = n ∈ Θ(n) 算法的整體效率： T(n) ∈ Θ(n2) 利用極限比較增長次數(shù) 前兩種情況意味著 t(n) ∈ O(g(n)) 后兩種情況意味著 t(n) ∈ Ω(g(n)) 第二種情況意味著 t(n) ∈ Θ(g(n)) 【 例 】 比較 (n1) 和 n2 的增長率 或證明： (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比 較 和 的 增 長 次 數(shù)2222log ( log ) 39。 非遞歸算法的數(shù)學(xué)分析 ?Example 1：討論下面這個算法（從 n個元素中查找最大元素問題）的效率。 4. 建立一個算法基本操作執(zhí)行次數(shù)的求和表達式。 Cbest(n) = 1 最差效率： 沒有相同元素或最后兩個元素相等。本例均為 n1 輸入規(guī)模： 方陣的階 n ?？紤]操作的時間耗費：大多數(shù)計算機的乘法比加法更 費時，算術(shù)運算比賦值操作更費時。 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)效率單獨研究 ?建立一個遞推關(guān)系式及相應(yīng)的初始條件 ?求解這個遞歸關(guān)系式，或者至少確定解的增長次數(shù) 漢諾塔 M(n)= 2M(n1)+1 , n1 1 ,n=1 M(n)=2n1 我們應(yīng)該謹慎使用遞歸算法，因為他們的簡潔可能會掩蓋他們的低效率。 ?最差、最優(yōu)與平均效率 ?增長次數(shù) ?符號 O， Ω， Θ ?非遞歸算法和遞歸算法的效率分析 ?遞歸算法簡潔性可能會掩蓋它的低效率 ?算法的經(jīng)驗分析是針對一個輸入樣本，運行算法的一個程序?qū)崿F(xiàn)，然后分析觀測到的數(shù)據(jù)。 ?算法可視法的種類： ?靜態(tài)算法可視法 ?動態(tài)算法可視法 (算法動畫 , Algorithm Animation) 靜態(tài)算法可視法 靜態(tài)算法可視法 動態(tài)算法可視法 小結(jié) ?算法效率包括時間效率和空間效率。 效率類別： 本例基本操作數(shù)只與輸入規(guī)模有關(guān)，與輸入元素分布無關(guān)， 不用分析最佳、最差和平均效率。 基本操作： 最內(nèi)層循環(huán)有三種操作：乘法、加法、賦值。下面分析 最差效率 Cworst(n) 平均效率： 其他情況 (略 ) 0 1 2 2 1nn????? ??? ? ?i j 外層 i 循環(huán)范圍 ： 0 →n – 2 內(nèi)層 j 循環(huán)范圍 ： i + 1 → n 1 建立增長函數(shù) —— 基本操作次數(shù)與輸入規(guī)模 n 的函數(shù)關(guān)系 ? ?? ?2 2 20 0 022001122202( 1 )( 1 ) ( 1 ) 1( 1 ) 1( 1 )2211( 1 ) ( 1 ) 1( 2 ) (( ) 11( 1 ) ( )1)2( ( 1 ) 1 ) ( 1 )1222n n ni i inwonjin niiristn i innnnnnnnnninCnn n nn? ? ?? ? ??????????? ? ? ? ?? ? ? ? ? ???? ? ? ? ???? ? ? ????? ????? ??? ? ?????20( 1 ) ( 1 ) ( 2 ) ( 3 ) 111 2 ( 1 ) ( 1 )2nin n n nninn?
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1