递回关系与演算法分析

2018/10/19,遞迴關係與演算法分析,1,遞迴關係與演算法分析,6,2018/10/19,遞迴關係與演算法分析,2,遞 迴 與 遞 迴 關 係,2018/10/19,遞迴關係與演算法分析,3,遞 迴 地 定 義,n!=n(n-1)! 或者 如果我們令 f(n)=n!，那麼 f(n)=nf(n-1)。 顯然地，這個函數的定義方式有一個特徵：我們所要定義的名相也出現在定義之中成為定義的一部分。 這就是我們所謂的遞迴地定義。,2018/10/19,遞迴關係與演算法分析,4,遞 迴 地 定 義,遞迴定義包括了兩個部分 基礎情況，在這裡明確地給出要定義的名相之某種型式的單純狀況值。 遞迴步驟，在這裡將要定義的名相之現值用之前的值來表示。 它跟歸納法的證明有著極高的相似性 ，因此遞迴定義也稱為歸納定義,2018/10/19,遞迴關係與演算法分析,5,數 列,在定義數列或者（更廣義來說的）物件序列時，遞迴是很重要的一個觀念。 所謂的物件序列 S 指的是一個有先後次序的物件序列，我們有第一個、第二個、乃至於第 n個物件。 S(n) 表示序列的第 n 個物件。 序列的定義通常是遞迴的 先明確地說出第一個或者前幾個值 然後再用前面的值來定義後來的值， 這中間當然會包括作用在這些物件上的一些運算。,2018/10/19,遞迴關係與演算法分析,6,數 列,2018/10/19,遞迴關係與演算法分析,7,數 列,類似像這個範例中命題 2 的規則，它用了前面一個或多個值來定義後續的數列值，我們稱這種規則為遞迴關係。,2018/10/19,遞迴關係與演算法分析,8,數 列,根據命題 1，數列的第一個數，T(0)，是1。 然後根據命題 2，數列的第二個數，T(1)=T(0)+3= 1+3=4。 再據命題 2，數列的第三個數，T(2)=T(1)+3=4+3=7。 繼續這麼做下去，我們可以發現數列T是 1, 4, 7, 10, 13, ,2018/10/19,遞迴關係與演算法分析,9,數 列,2018/10/19,遞迴關係與演算法分析,10,遞 迴 定 義,除了數列外，我們也可以用遞迴的方式來定義運算。,2018/10/19,遞迴關係與演算法分析,11,線 性 數 列,2018/10/19,遞迴關係與演算法分析,12,解 遞 迴 關 係,2018/10/19,遞迴關係與演算法分析,13,冪 級 數,一個多項式或者冪級數的係數可以是實數、複數、或者是諸如 Zn 等其它數系的元素。 多項式或者冪級數跟其它數系裡的數一樣，可以做相加以及相乘的運算。 我們尤其對於可以表示成有理函數的冪級數感興趣。,2018/10/19,遞迴關係與演算法分析,14,冪 級 數,2018/10/19,遞迴關係與演算法分析,15,冪 級 數,在使用上面這個等式要很小心，它不是對於所有的 x 值都成立的。 舉例來說，如果我們把 x 用 2 代進去，我們會得到,2018/10/19,遞迴關係與演算法分析,16,冪 級 數,這結果不是很荒謬嗎！ 事實上，這個級數只有當 -1x1 時才收斂到。 但是，在這以下我們將只是把這個等式視為是一種正式表示法，而不去管到底 x是在什麼範圍時這個收斂情況才成立。,2018/10/19,遞迴關係與演算法分析,17,冪 級 數,2018/10/19,遞迴關係與演算法分析,18,逆 二 項 式 級 數,在第四章我們介紹了二項式定理，利用它我們可以計算出 (1-x)n 的各項係數。 下面這個定理則可以計算出 的係數。,2018/10/19,遞迴關係與演算法分析,19,證 明,我們將用歸納法來證明這個定理。 當 n=1 時，左式正是上一個範例，而其逆二項式級數便是上個範例的幾何級數。 現在假設這個等式在一個給定的 n 值時成立，我們要證明在 裡的 xk 項之係數值為,2018/10/19,遞迴關係與演算法分析,20,證 明,我們有,2018/10/19,遞迴關係與演算法分析,21,證 明,其中，最後我們用到了表4.1中的等式VI（平行和）： 我們因此完成了這整個證明。,2018/10/19,遞迴關係與演算法分析,22,逆 二 項 式 級 數,2018/10/19,遞迴關係與演算法分析,23,2018/10/19,遞迴關係與演算法分析,24,證 明,如果 g(x) 是 f(x) 的乘法倒數，那麼 f(x)g(x)=1，因此 f(x) 跟 g(x) 相乘以後的常數項應該是1，而 f(x)g(x) 裡其它 x 的高冪次項係數必須為 0。 這是這些方程式的意思。由於 這個遞迴方程式決定了 g(x) 的各項係數。,2018/10/19,遞迴關係與演算法分析,25,範 例,利用這個演算法找出多項式 (1-x)2 的倒數。,2018/10/19,遞迴關係與演算法分析,26,冪 級 數,一個非零冪級數 f(x) 的乘法倒數是否一定是一個冪級數呢？倒不見得。 問題是出在冪級數的常數項有可能是 0，因此上面的演算法就派不上用場。 不過，這只是一個小問題。將 x 的最大可能次冪因子取出來，我們可以將 f(x) 重新寫成 f(x)=xnh(x) 其中 h(x) 有一個非零的常數項。,2018/10/19,遞迴關係與演算法分析,27,冪 級 數,h(x) 有一個倒數 k(x)，它是一個冪級數。 因此，f(x)的倒數可以寫成 x-nk(x) 像是這一類的級數我們稱之為勞倫斯級數。 以上我們所證得的是：任何一個非零的冪級數其倒數必然是一個勞倫斯級數。,2018/10/19,遞迴關係與演算法分析,28,冪 級 數,冪級數在離散數學這個領域扮演著非常重要的角色，因為每一個數列都有一個相對應的冪級數。 數列的性質跟冪級數的性質彼此就像一面鏡子一樣。 我們稱一個數列所對應的冪級數是這個數列的生成函數。,2018/10/19,遞迴關係與演算法分析,29,生 成 函 數,2018/10/19,遞迴關係與演算法分析,30,範 例,描述費蒙納西數列的生成函數。,2018/10/19,遞迴關係與演算法分析,31,範 例,因此 所以,2018/10/19,遞迴關係與演算法分析,32,範 例,2018/10/19,遞迴關係與演算法分析,33,範 例,2018/10/19,遞迴關係與演算法分析,34,範 例,2018/10/19,遞迴關係與演算法分析,35,範 例,2018/10/19,遞迴關係與演算法分析,36,生 成 函 數,請注意，費蒙納西數列、盧卡斯數列、以及尤拉數列它們的生成函數都是有理函數。,2018/10/19,遞迴關係與演算法分析,37,線性遞迴數列與生成函數,2018/10/19,遞迴關係與演算法分析,38,證 明,首先，假設是一個線性遞迴數列。這意味著存在正整數 r 與 N 以及常數 c1, c2, , cr 使得當 n N 時 這等於是說當 n N 時，在 裡 xn 的係數是 0。但是，這意味著f(x)Q(x)=P(x)，其中P(x)是一個多項式，因此f(x)=P(x)/Q(x)是一個有理函數。,2018/10/19,遞迴關係與演算法分析,39,證 明,現在假設生成函數 f(x) 是一個有理函數而且它的分母是 Q(x)。 由於 f(x)=P(x)/Q(x)，其中 P(x) 是一個多項式，因此 P(x)=f(x)Q(x)。 但是，這也意味著當 n N 時數列的各項滿足給定的遞迴關係。,2018/10/19,遞迴關係與演算法分析,40,倒 數 根,請注意，這個定理中分母 Q(x) 的根一定不會是 0。 將 Q(x) 做因式分解並且表示成這些因式的乘積： Q(x)=C(x-a1)(x-a2)(x-ar) 由於所有 Q(x) 的根 ak 一定不是 0，因此我們可以將上面的因是分解重寫為 Q(x)=D(1-a1-1x)(1-a2-1x)(1-ar-1x),2018/10/19,遞迴關係與演算法分析,41,倒 數 根,像這樣子將 Q(x) 分解成倒數根的型式是很方便的。 其中當然有些根，或者倒數根，是可以重複出現的。 在這種情況下，一個根的重複出現次數就稱為它的重複性。,2018/10/19,遞迴關係與演算法分析,42,部 分 分 數 分 解,2018/10/19,遞迴關係與演算法分析,43,比 奈 公 式,針對任何一個線性遞迴數列，我們可以如這個定理所述的找出它的各項並且將數列表示成這些項之和。 這種表示法也稱為比奈公式（Binets formula）。,2018/10/19,遞迴關係與演算法分析,44,費蒙納西數的比奈公式,費蒙納西數列的生成函數如下 其中我們希望能將 1-x-x2 因式分解成如下的型式,2018/10/19,遞迴關係與演算法分析,45,費蒙納西數的比奈公式,因此， 經過計算後，我們可以得到,2018/10/19,遞迴關係與演算法分析,46,費蒙納西數的比奈公式,因此 再根據部分分數分解定理，我們於是知道費蒙納西數列的生成函數可以表示成,2018/10/19,遞迴關係與演算法分析,47,費蒙納西數的比奈公式,將與帶入，我們可以計算得 因此,2018/10/19,遞迴關係與演算法分析,48,費蒙納西數的比奈公式,2018/10/19,遞迴關係與演算法分析,49,盧卡斯數列的比奈公式,2018/10/19,遞迴關係與演算法分析,50,盧卡斯數列的比奈公式,2018/10/19,遞迴關係與演算法分析,51,盧卡斯數列的比奈公式,2018/10/19,遞迴關係與演算法分析,52,尤拉數列的比奈公式,2018/10/19,遞迴關係與演算法分析,53,尤拉數列的比奈公式,2018/10/19,遞迴關係與演算法分析,54,尤拉數列的比奈公式,2018/10/19,遞迴關係與演算法分析,55,梯 子 圖,梯子圖（ladder graph）Ln包含平行的兩列頂點並且連結如下：,2018/10/19,遞迴關係與演算法分析,56,梯 子 圖,如果一個圖 G 的子圖F滿足： F 的頂點與 G 的頂點一樣； F 的邊彼此沒有交集且每一個 G 的頂點都屬於 F 的某一個邊（即，是F的某一個邊的端點） 那麼我們就說 F 是 G 的整體要素（one-factor）。,2018/10/19,遞迴關係與演算法分析,57,整 體 要 素,L1 的整體要素只有一個，就是它自己： L2 的整體要素有兩個： L3 的整體要素有三個：,2018/10/19,遞迴關係與演算法分析,58,整 體 要 素,L4的整體要素有五個：,2018/10/19,遞迴關係與演算法分析,59,梯 子 圖 之 整 體 要 素,證明梯子圖 Ln 的整體要素個數正是費蒙納西數 Fn+1。,2018/10/19,遞迴關係與演算法分析,60,梯 子 圖 之 整 體 要 素,2018/10/19,遞迴關係與演算法分析,61,演算法分析,2018/10/19,遞迴關係與演算法分析,62,演 算 法 分 析,遞迴關係的另外一個應用是演算法計算複雜度的分析。 在第五章，我們利用二元樹分析了搜尋以及排序問題的計算下限。 它所針對的是問題的分析，而我們這裡則是針對演算法做分析。 當我們分析排序問題的複雜度時，我們在意的是這個問題本身不管用什麼演算法來解它所需要的計算量； 但是，當我們分析一個排序演算法時，我們是針對一個演算法做分析，例如，快速排序演算法。,2018/10/19,遞迴關係與演算法分析,63,演 算 法 的 複 雜 度,正如同這個定義所蘊涵的，一個演算法的複雜度是估算成一個函數 f(n)，其中 n是輸入的長度。,2018/10/19,遞迴關係與演算法分析,64,演 算 法 的 複 雜 度,在探討一個演算法的複雜度時，我們最好是採用比較有效率的方法來估計該演算法在結束前所需要執行的步驟數目。 而這個有效率的方法一般指的就是O, , 這些近似符號。 請注意，O, , 這些近似符號不只可以用在演算法複雜度的描述上，也可以用在問題複雜度的描述上。,