數(shù)據(jù)結(jié)構(gòu)第一章-wenkub.com
2024-08-11 16:53 本頁面
【正文】 對任意正整數(shù)，則有 和 x?????? lo g22nnn??????lo g22nn n????附加：常見函數(shù) 常用公式： ① ② ③ ④ 調(diào)和級數(shù) ⑤ 102 2 1n ini????? 101()1nn iira r ar??????011222ni? 11 lo gnei ni ?? ??? 11 g(n)=logn+6 (2) f(n)=logn2。 Ω： 與 O 的定義對稱， 用它來評估算法的復(fù)雜性的話，得到的只是當(dāng)規(guī)模充分大時的一個下界，這個下界的階越高則評估就越精確，結(jié)果就越有價值。 f(n)∈ O(g(n)) → f(n)=O(g(n)) g(n)是 f(n)的漸近上界 ? f(n)=O(g(n))表明 ， 當(dāng) n→ ∞時 ， f(n)趨于無窮大的階不大于（即小于等于） g(n)趨于無窮大的階。 算法分析舉例： 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) ? 在算法分析過程中，通過抽象來簡化分析過程，忽略每個語句的實(shí)際開銷，代之以抽象的常數(shù) Cj； ? 不但忽略每個語句的實(shí)際開銷，將若干個 Ci的累加和抽象成常數(shù) a ? 對運(yùn)行時間的 增長量級 （速度）感興趣，只考慮運(yùn)行時間表達(dá)式中的 首項(xiàng)（比如， n2） ? 忽略首項(xiàng)系數(shù)，如，插入排序的最壞情況運(yùn)行時間（又稱最壞情況時間復(fù)雜度）為 Θ（ n2） 如： 常見函數(shù)增長率比較 常見函數(shù)增長率比較 常見函數(shù)增長趨勢圖例 漸近表示法 為了更清晰地表示算法運(yùn)行時間的增長率，引入漸近記號： 漸近記號 Θ Θnotation: 定義 ：給定一個函數(shù) g(n)， Θ(g(n))表示一個函數(shù)集合 Θ(g(n))＝｛ f(n) |存在正常數(shù) C1， C2和 n0使得當(dāng) n≥ n0，均有0≤ C1g(n) ≤f(n)≤C 2g(n)成立 ｝ 。處理出錯的方 法也不應(yīng)是中斷程序的執(zhí)行，而應(yīng)是返回 一個表示錯誤或錯誤性質(zhì)的值，以便在更 高的抽象層次上進(jìn)行處理 高效率與低存儲量： 效率指的是算法執(zhí)行時間；存儲量指 的是算法執(zhí)行過程中所需的最大存儲 空間 ? 解決同一個問題存在多種算法，如何評估各算法的好壞？或據(jù)此設(shè)計(jì)出更好的算法？ ? 運(yùn)行該算法所需要的計(jì)算機(jī)資源的多寡，所需越大復(fù)雜性越高 ? 最重要的資源：時間（處理器）和空間（存儲器） ? 評價一個算法優(yōu)劣的重要依據(jù)是看執(zhí)行該算法的程序需要占用多少機(jī)器資源： ? 程序所用算法運(yùn)行時所要花費(fèi)的時間代價 ? 程序中使用的數(shù)據(jù)結(jié)構(gòu)占有的空間代價 算法復(fù)雜度分析 算法復(fù)雜度分析
公司管理相關(guān)推薦
鄂ICP備17016276號-1