算法分析的基本概念和方法-資料下載頁
2025-05-12 22:06本頁面
【正文】 ????. 分析和求解復(fù)雜度的方法 ? [例 2] 利用遞歸關(guān)系來求基本操作的次數(shù) 求 Fibonacci數(shù)列的第 n項(xiàng)。該數(shù)列的定義為： F0= F1=1, Fi= Fi1 + Fi2， i ? 2。 由這一數(shù)學(xué)定義自然地導(dǎo)出一個(gè)遞歸算法。 int F ( int n ) { if(n==0||n==1) return 1。 else if(n=2) return F(n1)+F(n2)。 } 解： 該算法的計(jì)算時(shí)間 T(n)滿足遞歸方程： T(n)=T(n1)+T(n2)+1, n1； 初始條件 T(0)=T(1)=0。 . 分析和求解復(fù)雜度的方法 [例 3] 用平攤的辦法來統(tǒng)計(jì)基本操作的次數(shù)（ Amortized Analysis） () 整型數(shù)組 A(1： n)初始化為 n個(gè)正整數(shù)的集合 ,雙鏈表 List初始化為僅含一個(gè) 元素 0 for(j=1。j=n。j++) x=A(j)。 將 x 插入到表 List尾 if x 是偶數(shù) then while 表 List中 x的前面元素為奇數(shù) 在表 List中刪除 x的前面的那個(gè)元素 end while end if end for ? 解： 算法的基本操作為元素的插入和刪除操作。算法中插入操作的次數(shù)為 n 次，而刪除操作的次數(shù)最多為 n1次，所以，算法的基本操作最少 n次，最多 2n1次。 . 分析和求解復(fù)雜度的方法 1．典型的求和公式 ? 0? i ? n f(i) 二、求解算法復(fù)雜度的基本方法 . 分析和求解復(fù)雜度的方法 2. 積分近似求和 ? 如果連續(xù)函數(shù) f(n)是單調(diào)遞減的，則有 ? 如果連續(xù)函數(shù) f(n)是單調(diào)遞增的，則有 . 分析和求解復(fù)雜度的方法 . 分析和求解復(fù)雜度的方法 . 分析和求解復(fù)雜度的方法 . 分析和求解復(fù)雜度的方法 遞歸是一種重要的程序設(shè)計(jì)方法。有些問題的算法運(yùn)用遞歸過程來表示不僅自然簡(jiǎn)潔，而且也易于驗(yàn)證其正確性。遞歸算法的特點(diǎn)就是：易讀，易寫，易證。遞歸和歸納緊密相關(guān)。歸納定義的東西往往易寫出其遞歸的算法；而遞歸的算法往往可用歸納法來證明 。遞歸算法的時(shí)間復(fù)雜度分析往往需要借助于求解遞歸方程或者遞歸不等式的解得到。 遞歸方程的類型較多，涉及到的數(shù)學(xué)知識(shí)也較多。這里我們僅簡(jiǎn)單地介紹分析算法復(fù)雜度時(shí)常見的幾類簡(jiǎn)單遞歸方程的求法。 三、遞歸關(guān)系 . 分析和求解復(fù)雜度的方法 常用方法：展開法、差分方程法、換元法、數(shù)學(xué)歸納法等。 三、遞歸關(guān)系 . 分析和求解復(fù)雜度的方法 （ 1） 線性非齊次遞歸方程 主要解法：差分方程法、數(shù)學(xué)歸納法等。 . 分析和求解復(fù)雜度的方法 . 分析和求解復(fù)雜度的方法 . 分析和求解復(fù)雜度的方法 (optimal algorithm) 如果能夠證明求解問題 P的任何算法的時(shí)間是 ?(f(n)), 那么稱求解問題 P的時(shí)間為 O(f(n))的任一算法為問題 P的最優(yōu)算法。 一、最優(yōu)算法 (optimal algorithm) 可以證明，任何使用元素的比較給 n個(gè)元素的數(shù)組進(jìn)行排序的算法的最壞情況運(yùn)行時(shí)間一定是 ?(nlogn)。因此，歸并排序、堆排序算法都是最優(yōu)算法。 二、基于比較的排序問題
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1