數(shù)據(jù)結(jié)構第一章(參考版)
2024-08-15 16:53本頁面
【正文】 2 ( 1 ) 2 2n ini??? ? ? ?。 g(n)=3n n附加：常見函數(shù) 簡單函數(shù) ① na n的多項式函數(shù) ② log2n n的對數(shù)函數(shù) ③ 2n n的指數(shù)函數(shù) ④ Loglogn ⑤ log*n 附加：常見函數(shù) Floor and Ceiling x為實整型， 為小于等于 x的最大整數(shù)； 為大于等于 x的最小整數(shù)。 g(n)= (3) f(n)=nlogn+n。同時，數(shù)據(jù)結(jié)構應該適應求解問題的演變和擴展 ? 數(shù)據(jù)結(jié)構的設計和選擇也要比較算法的時空開銷的優(yōu)劣 習題 ? 用漸進記號表示 f(n)和 g(n)的關系 (1) f(n)=logn2。 插入排序運行時間 最好運行時間 Ω(n) 最壞運行時間 O(n2) 插入排序的運行時間在 Ω(n)和 O(n2)之間 漸近記號與不等號的類比 f(n)～ a， g(n)～ b f(n)= O(g(n)) ≈ a≤b f(n)=Ω(g(n)) ≈ a≥b f(n)=Θ(g(n)) ≈ a ＝ b 數(shù)據(jù)結(jié)構的選擇和評價 ? 仔細分析所要解決的問題，特別是求解問題所涉及的數(shù)據(jù)類型和數(shù)據(jù)間邏輯關系 ? 數(shù)據(jù)結(jié)構的初步設計往往在算法設計之先 ? 注意數(shù)據(jù)結(jié)構的可擴展性。 ? 若 f(n)=Θ(g(n))，則一定有 f(n)=Ω (g(n)) 漸近記號 Ω The curves for f(n)= Ω(g(n)) 漸近記號 Ω 例子： an3+bn2++d= Ω (n2), a0 例子： an3+bn2++d= Ω (2n2＋ 3nlogn), a0 漸近記號 比較 O： 用它來評估算法的復雜性的話，得到的只是當規(guī)模充分大時的一個上界，這個上界的階越低則評估就越精確，結(jié)果就越有價值。 ? 若 f(n)=Θ(g(n))，則一定有 f(n)=O(g(n))，反之不成立 漸近記號 O The curves for f(n)=O(g(n)) 漸近記號 O 例子： an3+bn2++d= O(n3), a0 例子： an2+bn+c= O(n3), a0 例子： nlgn＝ O(n2), 但是 nlgn≠Θ(n2) 漸近記號 Ω Ω notation: 定義 ：給定一個函數(shù) g(n)， Ω (g(n))表示一個函數(shù)集合 Ω (g(n))＝｛ f(n)|存在正常數(shù) C和 n0使得當 n≥ n0，均有 0≤Cg(n)≤f(n)成立 ｝ 。 漸近記號 O Onotation: 定義 ：給定一個函數(shù) g(n)， O(g(n))表示一個函數(shù)集合 O(g(n))={f(n) |存在正常數(shù) C 和 n0 使得當 n≥ n0，均有0≤f(n)≤Cg(n) 成立 }。 f(n)∈ Θ(g(n)) → f(n)=Θ(g(n)) g(n)是 f(n)的漸緊界 ? f(n)=Θ(g(n))表明 ， 當 n→ ∞時 ， f(n)和 g(n)趨于無窮大的階是相同的。 算法復雜度分析 算法分析舉例： InsertionSort ? 洗牌： 算法分析舉例： 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 除了待排序的數(shù)據(jù)，只用了一個附加的存儲單位。運行時間的下界 ? 最壞運行時間 同樣的輸入規(guī)模，不同的數(shù)據(jù)分布情況下，最慢或運行步數(shù)最多時的運行時間。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實際上已被嵌入算法中 ? 輸出 ? 一個或多個輸出，與
公司管理相關推薦
鄂ICP備17016276號-1