【正文】 ei ni ?? ??? 11 算法分析舉例： InsertionSort InsertSort on the array A= 5,2,4,6,1,3 算法分析舉例： InsertionSort ? INSERTIONSORT(A) ? 1 for j← 2 to length[A] ? 2 do key ← A[j] ? 3 ★ Insert A[j] into the sorted sequence A[1… j1] ? 4 i ← j1 ? 5 while i0 and A[i]key ? 6 do A[i+1] ← A[i] ? 7 i ← i1 ? 8 A[i+1] ← key Cost C1 C2 0 C4 C5 C6 C7 C8 Times n n1 n1 n1 同上 n1 2njj t??2( 1)n jjt???算法分析舉例： InsertionSort 最好情況 ：如果輸入序列已經(jīng)有序，則 tj ＝ 1 算法分析舉例： InsertionSort 最壞情況 ：如果輸入序列為降序，則 tj ＝ j 平均情況 ：與數(shù)據(jù)的概率分布有關(guān)，假設(shè)對 所有 j=2,3?n 有 tj=j/2 復(fù)雜性漸近性態(tài) ? 在算法分析過程中，通過抽象來簡化分析過程，忽略每個(gè)語句的實(shí)際開銷，代之以抽象的常數(shù) Cj； ? 不但忽略每個(gè)語句的實(shí)際開銷，將若干個(gè) Ci的累加和抽象成常數(shù) a ? 對運(yùn)行時(shí)間的 增長量級 （速度）感興趣，只考慮運(yùn)行時(shí)間表達(dá)式中的 首項(xiàng)（比如， n2） ? 忽略首項(xiàng)系數(shù)，如，插入排序的最壞情況運(yùn)行時(shí)間（又稱最壞情況時(shí)間復(fù)雜度）為 Θ（ n2） 如： 常見函數(shù)增長率比較 常見函數(shù)增長率比較 常見函數(shù)增長趨勢圖例 漸近表示法 為了更清晰地表示算法運(yùn)行時(shí)間的增長率，引入漸近記號： 漸近記號 Θ Θnotation: 定義 ：給定一個(gè)函數(shù) g(n)， Θ(g(n))表示一個(gè)函數(shù)集合 Θ(g(n))＝｛ f(n) |存在正常數(shù) C1， C2和 n0使得當(dāng) n≥ n0，均有0≤ C1g(n) ≤f(n)≤C 2g(n)成立 ｝ 。ImagPart ) 初始條件：復(fù)數(shù)已存在。 ? 問題抽象 、數(shù)據(jù)抽象、算法抽象 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)結(jié)構(gòu) 是相互之間存在一種或多種特定 關(guān)系 的數(shù)據(jù) 元素 的集合 ? 數(shù)據(jù)的 邏輯結(jié)構(gòu) ? 圖 ?樹 ?二叉樹 ?線性表 ? 數(shù)據(jù)的 存儲(chǔ)結(jié)構(gòu) ? 順序方法、鏈接方法 ? 數(shù)據(jù)的 運(yùn)算 ? 增、刪、查、改 ? 排序、檢索 存儲(chǔ) 數(shù)據(jù)結(jié)構(gòu) 邏輯 運(yùn)算 ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu)可以用一組數(shù)據(jù)（表示為結(jié)點(diǎn)集合 D），以及這些數(shù)據(jù)之間的一組二元關(guān)系（關(guān)系集合 S）來表示： ( D ， S ) ? 其中 ? D 是數(shù)據(jù)元素的有限集， 是由有限個(gè)結(jié)點(diǎn)組成的集合，每一個(gè)結(jié)點(diǎn)都代表一個(gè)數(shù)據(jù)或一組有明確結(jié)構(gòu)的數(shù)據(jù) ? S 是 D上關(guān)系的有限集， 是定義在集合 D上的一組關(guān)系，用它描述結(jié)點(diǎn)數(shù)據(jù)之間的邏輯關(guān)系 Data_Structures = (D, S) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的邏輯結(jié)構(gòu) ? 元素的數(shù)據(jù)類型 ? 高級語言中指數(shù)據(jù)的取值范圍及其上可進(jìn)行的操作的總稱 ? 例 C語言中 ? 基本數(shù)據(jù)類型： int, char, float等 ? 構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、枚舉 ? 指針、空 (void)類型 ? 用戶也可用 typedef 自己定義數(shù)據(jù)類型 ? 結(jié)點(diǎn)的類型可以是基本數(shù)據(jù)類型，也可以根據(jù)應(yīng)用的需要來靈活定義 typedef struct { int num。Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) v1 和 v2 的值。 算法的特性 ? 算法的特性（續(xù)） ?