宣告：本篇文章花費作者大量時間精力，所以是不可以轉載的哦，以下內容有些概念較為燒腦，可能引起不適，請在奧特曼陪同下閱讀（QAQ），，，

目錄

零.前言

1.計算復雜性函式的階

1.增長的階

1.增長率

2.常見的階

2.增長函式

1.增長函式的性質

2.Θ階（同階函式集合）

1.定義：

2.解釋

3.例題

3.大O階（低階函式集合）

1.定義：

2.解釋

3.Θ階與O階的關系

4.Ω階（高階函式集合）

1.定義

2.解釋

3.θ階，大O階，Ω階的關系

5.小o階（嚴格低階函式集合）

1.定義：

2.解釋

3.例題

6.小ω階（嚴格高階函式）

1.定義：

2.解釋

7.漸進符號的性質

1.傳遞性

2.自反性

3.對稱性

4.反對稱性

2.和式的估計與運算

1.為什么要進行和式的估計與運算

2.和式的估計

1.線性和

2.級數

?

3.和的界限

4.直接求和的界限

3.遞回方程

1.遞回的定義

2.遞回方程的形式

3.遞回方程的初始條件

4.求解遞回方程的三個主要方法

1.替換（代入）方法

2.細微差別的處理

3.例題：

3.變數替換方法

2.迭代（遞回樹）方法

1.步驟

2.遞回樹求解

3.例題

3.Master定理方法

1.適用型別

3.定理內容

4.一張圖記憶

5.例題

4.總結

---

零.前言

這是演算法設計與分析的第二講，我們知道演算法的設計是與數學分不開的，一個人的演算法水平的下限是對模型掌握的多少，上限就是他的數學水平（我們演算法大佬說的），那么就有人說了，我的數學水平也不高啊，怎么學好演算法？數學水平不高有問題嗎？沒有問題，看了這篇文章，搞定演算法分析的數學基礎，

1.計算復雜性函式的階

1.增長的階

1.增長率

描述演算法效率的方法：增長率

而我們引入階的概念，就是為了研究演算法的增長率，注意不是描述執行的時間，因為一個演算法執行的時間不僅與演算法本身有關，還和其他因素有關（比如硬體性能和使用的語言等），我們希望只根據演算法本身來描述演算法的好壞，因此沒有選擇時間作為參考，但其實描述演算法運行效率的指標，就是拋棄其他所有因素演算法所運行的時間，只不過這個時間沒有辦法準確計算，所以用時間的增長率代替，

所謂增長率，就是隨著輸入指標n的逐漸增大，運行時間的增長率，而非運行時間本身，

而程式運行的純時間（不考慮其他因素），與代碼的陳述句執行次數成正比，下圖()內的內容表示的就是一個程式的大概執行陳述句數，所以可以用含有n的運算式代表演算法的執行效率（可以看看資料結構部分），而增大輸入規模后純運行時間的增長率就等價于執行代碼數的增長率，不知道你聽懂了沒有呀，

增長率即為當多加入一組數所需要增加的大致時間或者增加的代碼大致執行條數，還要注意一下，這里的增長率只的是廣義的增長率，不能嚴格的按照數學方式來計算增長率，如果很細地計算的話幾乎沒有一段代碼的準確增長率是相同的，為什么可以這么做呢？因為一點點的不同對運算的純時間影響并不大，所以可以將它們歸于一類復雜度，

2.常見的階

我們來看這一段θ()階，會發現

1.從左到右演算法的復雜度越來越高，即與()中復雜度為同階的演算法的運行效率越來越低，

2.所有階的復雜度都是初等函式的集合，

每一個()里的內容表示按演算法復雜度分出來的一類函式，θ()表示這一類函式的集合，

當你把一個本應該是n^2的演算法復雜度搞成nlgn的時候，你就是一個超級大佬了（我們老師說的），

2.增長函式

1.增長函式的性質

1.輸入規模大，

2.不考慮低階項和常系數，

3.只考慮高階項

增長的記號：Θ，O，Ω，o，ω

2.Θ階（同階函式集合）

所謂Θ()，就是與()內運算式運算時間增長率相同的運算式的結合，一個運算式代表一個程式的時間復雜度，

1.定義：

Θ(g(n))={f(n)|存在c1,c2>0,n0,當任意n>n0時，c1g(n)>f(n)>c2g(n)}，成為與g(n)同階的函式集合，即滿足條件的所有f(n)都與g(n)同階，

用影像來表示一下：

2.解釋

這里表示的是f(n)與g(n)，Θ階所描述的就是同階函式，n0之前的內容不需要看，因為輸入資料過小是沒有辦法分析時間復雜度的，

顯然c1g(n)和c2g(n)的增長率是相同的，因為計算時間復雜度的時候是去掉常數的，所以c1g(n)與c2g(n)都是g(n)型別的，既然屬于同一個型別，那么增長率（注意是廣義的增長率）一定相同，

由于f(n)始終在兩個增長率相同的函式中間，所以f(n)的增長率與這兩個函式相同，即f(n)也屬于g(n)的型別，所以f(n)與g(n)是同階的，

3.例題

1.證明：(1/2)n^2-3n=θ(n^2)

即證存在c1和c2，n0>0，當n>n0時對任意n使得c1n^2<(1/2)n^2-3n<c2n^2

所以c1<1/2-3/n<c2，存在n0=7，即n>7時，存在c2=1/2，c1=1/14使得原式成立，所以得證，

2.證明：6n^3!=θ(n^2)

若存在c1和c2，n0>0，當n>n0時對任意n，使得c1n^2<6n^3<c2n^2，

所以c1<6n<c2.當n>c2/6時，與6n<c2矛盾，所以得證，

3.大O階（低階函式集合）

1.定義：

O(g(n))={f(n)|存在正常數c和n0滿足對于所有n>=n0，0<=f(n)<=cg(n)}，記作：f(n)屬于O(g(n))，或者f(n)=O(g(n))，

用影像表示為：

我們引入其他階的目的在于，有一些程式的復雜度無法直接計算得到但是可以獲得其復雜度的取值范圍，

2.解釋

顯然，當n>n0時f(n)一直在cg(n)的下方，而cg(n)與g(n)是同階的（即增長率是廣義相同的），所以隨著n的增大代碼執行量的增長率f(n)是<=g(n)的，即時間的增長率是小于等于g(n)，所以f(n)的效率低于g(n)，O(g(n))代表的是所有復雜度小于等于g(n)的函式的集合，

3.Θ階與O階的關系

1.f(n)=θ(g(n))，則f(n)=O(g(n))，

因為f(n)與g(n)同階復雜度相同，O(g(n))包含所有復雜度小于等于g(n)的函式，f(n)是屬于O(g(n))的，

2.Θ標記強于O標記

因為Θ階計算的是同階，而O階計算的是最高階，好比做一份作業，Θ階表示明確地知道一小時可以做完，但O階只知道十小時內可以做完，所以Θ階是優于O階的，

3.Θ(g(n))屬于O(g(n))

對于同一個g(n)O階的范圍比θ階大，

4.an+b=O(n^2)

因為an+b的演算法復雜度是Θ(n)型別的，O(n^2)包含所有比n^2復雜度低的函式，所以對于an+b這樣演算法復雜度是n的演算法是被O(n^2)包含在內的，同理n=O(n^2)，

5.O(n)=O(n^2)但是O(n^2)!=O(n)

前面講過了等號是包含的意思，是后者包含前者，不能調換順序，

6.O標記表示漸進上界，Θ標記表示漸進緊界，

7.Θ階表示的是基本運算時間，但O階表示的是最壞的結果即最長運行時間，

4.Ω階（高階函式集合）

1.定義

Ω(g(n))={f(n)|存在正常數c和n0，對于所有n>=n0，0<=cg(n)<f(n)}記作f(n)∈Ω(g(n))或者f(n)=Ω(g(n))，

用影像來表示是這樣的：

2.解釋

對比大O階，Ω(g(n))表示的是所有比g(n)低階的函式的集合，

3.θ階，大O階，Ω階的關系

1.對于f(n)和g(n)，f(n)=Θ(g(n))，當且僅當f(n)=O(g(n))，f(n)=Ω(g(n))，

f(n)比g(n)階高，同時比g(n)階低，所以g(n)與f(n)是同階的，反之也成立，

2.O表示漸進上界，Θ表示漸進緊界，Ω表示漸進下界，

3.Ω用來描述的是運行時間最好的情況，

對于插入排序，它的演算法復雜度既屬于O(n^2)又屬于Ω(n)，

5.小o階（嚴格低階函式集合）

1.定義：

o(g(n))={f(n)|對于任意正常數c，存在一個整數n0，從而對所有n>=n0，滿足0<=f(n)<cg(n)}，記作f(n)∈o(g(n))，或者f(n)=o(g(n))，

用影像來表示是這樣的：

2.解釋

我們發現這個定義和大O階的定義很相似，只不過將存在一個c改成了任意c（注意對于每一個c都有一個n0與之對應），o(g(n))代表的意思是所有復雜度小于g(n)的函式的集合，而O(g(n))表示的是所有復雜度小于等于g(n)的集合，兩者只差了一個等號，

在大O階中，存在一個c使得cg(n)>f(n)，這個時候f(n)的增長率可以小于cg(n)（即g(n)的增長率）這樣f(n)就永遠小于g(n)了，但f(n)的增長率也可以等于（廣義上的）cg(n)，這種情況下兩者基本是平行的，f(n)依然一直小于cg(n)（同時也是g(n)），因為c本身是固定的，

在小o階中，對于任意c都有cg(n)>f(n)，當f(n)的增長率小于cg(n)時（g(n)），f(n)將永遠小于g(n)，當f(n)的增長率等于g(n)時，那么對于一個很小的c來說，f(n)就有機會大于cg(n)（g(n)）,這就是兩者的區別，

總結一下，

大O(g(n))包含的函式：f(n)的增長率（復雜度）<=g(n)，

小o(g(n))包含的函式：f(n)的增長率（復雜的<g(n），

3.例題

1.證明：2n=o(n^2)

對于任意c>0,存在一個n0當n>n0時，使得2n<c(n^2)

即2<cn，即2/c<n

對于任意的c總存在一個n0=2/c使得不等式成立，所以得證，

2.證明：2(n^2)!=o(n^2)

若成立則，對于任意的c，存在一個n0，當n>n0時，使得2(n^2)<c(n^2)

即2<c，當c=1時不成立，與對任意c都成立矛盾，所以得證，

6.小ω階（嚴格高階函式）

1.定義：

ω(g(n))={f(n)|對于任意正常數c，存在一個整數n0，從而對所有n>=n0，滿足0<=f(n)<cg(n)}，記作f(n)∈ω(g(n))，或者f(n)=ω(g(n))，

2.解釋

與小o階是一樣的，表示的是不緊的下界，大Ω(g(n))表示的是所有階數大于等于g(n)的函式的集合，小ω階表示所有階數大于g(n)的集合，即n^2=Ω（n^2）但是n^2!=ω(n^2)，

7.漸進符號的性質

1.傳遞性

傳遞性對于五個階來說都是通用的

比如f(n)=Θ(g(n))，且g(n)=Θ(h(n))，則f(n)=Θ(h(n))，

2.自反性

對于Θ，O，Ω階有自反性，f(n)=Θ(f(n))，

3.對稱性

只對Θ階，f(n)=Θ(g(n))，則g(n)=Θ(f(n))，

4.反對稱性

f(n)=O(g(n))，當且僅當g(n)=Ω(f(n))，

f(n)=o(g(n))，當且僅當g(n)=ω(f(n))，

2.和式的估計與運算

1.為什么要進行和式的估計與運算

和式的估計與運算在我們計算一段代碼的復雜度中經常用到，我們之前所謂的f(n)，g(n)函式的集合都是一段代碼的執行步驟的和，然后才能進行一些大O階什么之類的運算，說白了就是要先計算程式一共執行了多少段代碼，再對結果進行分類，因此掌握計算和式的方法是非常必要的，以下內容均為計算和式（演算法的復雜度）的常用數學方法，

2.和式的估計

1.線性和

這是最基本的數學公式，看來演算法和高數的關系也是相當巨大呀，，博主就直接放圖片了，這個求和符號太難打了，，

2.級數

提一下最后一個，叫調和級數，高數里總考判斷題的那個級數就是這個東西，

這幾個就是高中時算的最6的那幾個，裂項相消啊，總之前后消去，剩下首尾，

3.和的界限

例題一：

還是貼圖片吧，這個Σ的上下內容沒法打，看著也比較費勁，能把人繞暈，，

我們來分析一下這道題：即直接根據定義往里套就行，存在一個c，n0使當n>n0的時候，左式小于等于c3^n即可，證明程序如下：

這段證明運用到了數學歸納法，即先確定首元素滿足，然后再證明在前一個元素滿足的條件之下，后一個元素也滿足，則所有元素就都滿足了，這其實沒有證明完畢，當最后的式子成立才滿足條件，即存在一個c使最后一步的式子成立我們可以發現當c>=3/2時都成立，所以得證，

例題二：

這是一段錯誤證明的式子，看了這個ppt是不是很懵，常數c?什么常數c，只有視力不好的人才能看到常數c，像我這樣的國家代碼之才，還常數c?其實做這樣的題目的時候一定要拆開了來看，特別要注意=O(n)中的等號不是等號，是賦值符號，注意下面的式子第二個等號代表的意思是，存在一個常數c1使得Σk+(n+1)<=c1n+(n+1)，這段是沒問題的，問題出現在下一個等號上，如果下一個等號成立，意味著存在常數c2，使得c1n+(n+1)<=c2n，即(c1+1-c2)n<=-1恒成立，由于c1,c2都是常數，值未知，所以不能保證隨著n的增大不等式始終成立，也可以這樣理解，因為c1和c2的大小未知，所以不能確定c1n+(n+1)<=c2n恒成立，

4.直接求和的界限

這兩個式子很重要，大家一定要記牢啊！

例題1：

這種題代表一類題型，也是我們高中經常要看的一種消去法，（用演算法大佬的話來講，他的每一道題都不可能白出），這道題是將每一個式子都列出之后再相除進行消去，只剩下了首項和尾項，即得到的結果是ak/a0<=r^k，然后兩邊再分別套積分號來計算，最終得到結果，其中最后計算r的積分的式子應用到了前面的內容，這種題的解題思路就是先找到與ak等價的式子，根據題中的不等式找關系，然后再套積分號，最終根據常數的計算公式來進行求解，

例題2：

和上一題是同一個型別，首先找出與積分式等價的式子，設每一個通項是bk，只需用b(k+1)/bk得到這個值<=2/3，然后將k=1,2,3,4,,,依次帶入相除，找到b(無窮）/b1的值，經過博主與舍友的討論認為這個答案有湊數的嫌疑，不算準確的答案，最后一個運算式中的k應該改為k-1，即(1/3)*(2/3)^(k-1)，那樣的話上界就不是一了，但是對于程式來說其實都是大O(1)所以問題不大，

例題3：

這里采用了放縮的方法，放了一半的元素，注意這不是數學題，不需要那么精確地計算出結果，只要算出來階數即可，利用上面的那兩個運算式就可以證明出下界是Ω(n^2)，

例題4：

同樣的套路，先用a(k+1)/ak得到一個運算式，尋找從哪一項開始這個運算式是小于1的（因為我們已經猜測運算式的上界是O(1）)，然后將它們拆開，前一項是一個常數，不用管，后一項的值始終小于1，因此它的上界是O(1)，

例題5：

這題是所有題中最讓我懵逼的一道，沒點數學基礎真不敢出來混，觀察這組資料，每一個括號中第一個數是2的倍數，每個括號含有的項數也是二的倍數，這兩個二的倍數是相等的，這里的i代表有多少組資料，設有m組資料則1+2^1+2^2+....2^(m-1)=n所以解出m=log(2)(n+1)，下面是2，上面是（n+1），所以第一個不等式成立（吐槽一下這題老師是念ppt講的，連log下面的2沒了都沒發現），前一個Σ符號表示的是有幾組數，后面的Σ符號表示的是每一組數加起來，1/(2^i+j)表示的是每一個數，這樣你是不是就通透了呀，

例題6：

證明上述式子，先看前一個不等號，前面的式子表示的是一個積分，是連續的，后一個表示的是散點相加，我們知道積分的值表示的是函式影像與x軸圍成的面積，我們對散點相加的乘以1，那么它也會表示一個面積，如第一個圖所示，除去相同部分我們發現前一個積分面積剩下m-1到m-2這個梯形的面積，后面的散點圖運算式剩下的是(n-m)個小三角，由于n是趨近于無窮大的，所以小三角的面積和一定大于(m-1)到(m-2)這個梯形的大小，當n是常數時無法判斷，

第二個圖我認為畫的有點問題，我們還是按照第一個圖來理解，當除去相同的部分之后，散點圖剩下(n-m)個小三角，積分圖剩下最后一個梯形，將小三角往梯形里填充，很明顯發現它們的面積和是小于梯形面積的（注意我們目前研究的是遞增函式），當n時常數的時候也是如此，

既然遞增函式的結果是這個，那么遞減函式的結果就是將它們反過來，即：

例題7：

兩個結論，經常用到，記住就會，記不住就不會，

3.遞回方程

1.遞回的定義

遞回定義是數理邏輯和計算機科學用到的一種定義方式，使用被定義物件的自身來為其下定義（簡單說就是自我復制的定義），遞回定義(recursive definition)亦稱歸納定義，一種實質定義，指用遞回的方法給一個概念下的定義，

2.遞回方程的形式

T(n)=T(n/a)+bn+..

即有兩個T()的函式項，遞回方程研究了T(n)與T(<n)的函式關系，

3.遞回方程的初始條件

遞回方程需要有基本情況或者初始條件，

比如假設T(n)=T(n/2)+11n最后計算出T(n)=1

與T(n)=T(n/2)+11n計算出T(n)=10000這兩個式子雖然是不同的，

但是兩者的T(1)=O(n)，因此我們可以忽略具體的值，

4.求解遞回方程的三個主要方法

1.替換（代入）方法

步驟：（1）猜想

（2）數學歸納法證明

猜想的方法：

1.聯想已知的T(n)

例題：求解T(n)=2T(n/2+17)+n

我們發現T(n)=2T(n/2+17)+n與T(n)=2T(n/2)+n只差了一個17，而后者的上界是O(nlgn)，隨著n的增大，這個17所產生的影響越來越小，所以我們猜測原式的時間復雜度是O(nlgn)，

2.先證明不確定的上下界，然后縮小不確定性的范圍

例題：求解T(n)=2(n/2+17)+n

首先證明比較容易的上下界，首先計算出T(n)=Ω(n)，然后計算出T(n)=O(n^2)，而nlgn的復雜度剛好在n和n^2之間，所以估計出其上限是O(nlgn)，

2.細微差別的處理

當我們的猜測是正確的時候，但是數學歸納法無法證明出來，

解決方法：從猜想中減去一個低階項，

3.例題：

向上向下取整的符號了，我也不會列印，所以還是貼圖片吧，，，，

ppt還是寫的太簡潔了，我把他詳細地說一說，首先我先猜想T(n)=O(n)，即猜測存在一個c，對于任意的n，存在一個n0使得T(n)恒小于等于O(n)，即T(n/2)[向下取整]<=c(n/2)[向下取整]，T(n/2)[向上取整]<=c(n/2)[向上取整]，我們想證明猜想成立也就是要證明T(n)<=cn成立，但是這樣只能證明出T(n)<=cn+1，所以證明的不對，

下面就需要應用到細微差別處理的方法：

注意這里雖然減去了一個常數項，(cn-b)表示的依然是O(n)，如果假設T(n)=O(n)，此時假設的是存在一個c，對于任意的n存在一個n0使n>=n0的時候，T(n)<=cn-b<=cn，證明了T(n)<=cn-b也就證明了T(n)<=cn，要證明猜想成立就要證明T(n)<=cn，

我們觀察式子，T(n)<=cn-2b+1，由于b是任取的整數，所以當b>=1時，T(n)<=cn-b<=cn，所以成立，T(n)=O(n)，

3.變數替換方法

顧名思義，通過變數替換，將遞回方程變換為熟悉的方程，

例題：求解T(n)=T(√n)+lgn

令m=lg(n)，則n=10^(m)，√n=10^(m/2)，所以原式變成了T(10^(m))=T(10^(m/2))+m

令S(m)=T(10^m)所以原式為，S(m)=S(m/2)+m，所以S(m)=O(mlgm)，所以T(10^m)=O(mlgm)，因為10^m=n，所以T(n)=O(lgn*lg(lgn))，

2.迭代（遞回樹）方法

1.步驟

1.畫出遞回樹，

2.回圈地展開遞回方程，

3.將遞回方程轉化為和式，

4.使用求和技術求解，

2.遞回樹求解

整個式子的時間復雜度就是將所有的節點加在一起，下面我們來分析一下，為什么會畫出這樣一棵樹：

首先T(n)包含四個部分，前三個部分是T(n/4)[向下取整]，即樹的分叉部分，最后一個部分是樹根部分，即為Θ(n^2)部分，由于所有的樹的分叉部分都代表了一棵樹，所以其實最后加起來的部分只有樹根部分，對于第一次遞回來說，三個樹杈部分又是一個樹，即T(n/4[向下取整])=3T(n/16[向下取整])+Θ((n/4)^2[向下取整])，而后者等于Θ((n/4)^2)，因此它對應的樹根節點就是c(n/4)^2，依次類推，知道最終節點變成了T(1)，這是因為原本n是一個很大的數，當走到T(1)時拆分之后的結果就變成了0，無法再分出樹杈了，

因此整道題的求解程序是：

首先計算樹的高度，n/4^(m-1)=1，解得m=log(4)(n)+1.

然后計算最后一行的元素個數：m=3^(log(4)(n)+1-1)=3^(log(4)(n))=n^(log(4)(3))，兩邊同時取log(4)，你就會解了，

這是整道題的程序，是不是數學很重要，，不看很難解出來，

3.例題

用我拙劣的迷之畫風來畫一下這棵樹：

后面幾個框里都是n/16向下取整，，畫太丑了，不畫了，，

注意這里的每個節點是帶有向下取整的符號的，和上一題不同，上一題的常數項是 Θ(n^2)就算是向下取整后依然是c(n^2)，但是這里是n所以列出來的式子是：

注意這里有兩個他ppt寫錯了，是向下取整，不是絕對值，

所以最終上限是O(n)，

3.Master定理方法

1.適用型別

T(n)=aT(n/b)+f(n)，

其中a表示子問題數量，b表示子問題從原問題縮小的比例，f(n)表示將問題分解和子問題分解整合的代價，其實這些都不用管，記住上面的形式即可，

3.定理內容

前提：a>=1且b>1，T(n)定義在非負整數集合上，

1.當f(n)=O(n^(log(b)(a)-ε))時（ε>0是一個常數），即f(n)<=cn^(log(b)(a)-ε)時，T(n)=Θ(n^(log(b)(a))，

2.當f(n)=Θ(n^(log(b)(a))時，則T(n)=Θ(n^log(b)(a)lgn)，

3.當f(n)=Ω(n^(log(b)(a)+ε))時，ε>0是一個常數，且對于所有充分大的n，af(n/b)<=cf(n)，c<1是常數，則T(n)=Θ(f(n))，

注：下劃線部分為正則條件，即必須滿足的條件，

ε存在一個即可，

4.一張圖記憶

這張圖總結的到位，點個贊，注意最后一個式子的正則條件，還有第一個和第三個式子使用時的

ε別忘了，

5.例題

例題1：

T(n)=9T(n/3)+n

此時a=9，b=3，f(n)=n，

n^(log(b)(a))=n^2，存在ε使得f(n)=n=O(n^(2-ε))，

符合第1種情況，所以T(n)=Θ(n^2)，

例題2：

T(n)=T(2n/3)+1

此時a=1，b=3/2，f(n)=1.

n^(log(b)(a))=1，此時f(n)=Θ(n^(log(b)(a))，

符合第二種情況，所以T(n)=Θ(lgn)，

例題3：

T(n)=3T(n/4)+nlgn

此時a=3，b=4，f(n)=nlgn

n^(log(b)(a))=n^(log(4)(3))，存在ε使得f(n)=Ω(n^(log(4)(3)+ε))，這是因為nlgn的復雜度是大于n的，所以存在ε使之大于n^(log(4)(3)+ε，

此時還要證明正則條件af(n/b)<=cf(n)，c<1

即證(3n/4)lg(3n/4)<=cnlgn，化簡一下，當c=3/4時，成立，注意c也是存在而不是任意，

所以T(n)=Θ(nlgn)，

例題4：

T(n)=2T(n/2)+nlgn

此時a=2，b=2，f(n)=nlgn

n^(log(b)(a))=n，不存在ε使得f(n)=Ω(n^(1+ε))，

所以Master定理不好使，

4.總結

經過兩個星期的奮戰，終于搞定了這篇博客，不得不說寫這篇博客真的很燒腦，因為好多老師在課上一筆帶過的知識點，博主基本上都給出了嚴格的證明（有的是和同學一起討論的），吐個槽這ppt做的實在是太簡便了，，，還有點錯誤，不過在博主的火眼金睛之下都給他找到了，并在博文中用紅筆標注了出來，寫完這篇博客我感覺自己的演算法水平還是有所提高，如果你真的讀完了呢，相信再碰到類似的問題也能夠輕松求解吧（比心），

如果可以的話，三連關注一下吧（卑微微），如果你發現博文有錯誤，也歡迎私聊博主呀！