大家好，我還是那個快樂學編程，學到無極限的@jxwd~~~😄

題外話：

在接下來的2個月多里，小編會持續推出資料結構于演算法以及C++的內容，關注我，訂閱專欄，就能持續看到我的文章啦~~~

對于資料結構與演算法，小編仍會采用章節式的體裁來介紹講解，

我們把資料結構與演算法和C++的學習融合在一起，

即先學一部分的資料結構與演算法的基礎內容（學到二叉樹），這之前的代碼我們都將以C語言的形式實作，然后在此基礎上去學習C++，包括它的各種語法和STL，然后再用C++來完成后面部分復雜的資料結構的學習（因為C不夠靈活），

本節為資料結構于演算法的第一節

所有的資料結構章節均對《大話資料結構》和《資料結構與演算法分析》有一定參考，

來一波口號：jxwd，讓你服氣，拒絕水文，從我做起！~~~

看我的博客，就基本不用啃讀課本啦

看了我的博客，課本你會當小說一樣的把它順暢地看完

當然，前提是我說的你也要能夠接受，放心，只要你認真讀下去，你就能非常容易地看懂

話不多說，我們正式開始，

目錄

資料結構前言：

——演算法的時空復雜度

演算法效率

演算法的特性

演算法的時間復雜度

演算法的空間復雜度

資料結構前言：

學習資料結構之前，需要問一問自己，何為資料結構？

實際上，資料結構，Data Structure, 指的就是計算機存盤、組織資料的一種方式，并且可以理解為，這些資料的元素間有著特定關系，而這些資料包含其特定關系的集合，就叫資料結構，

那演算法呢？我們在學習資料結構的時候，總能聽到：資料結構與演算法這樣的說法，

即意為資料結構于演算法不分家，

那么演算法(Algorithm)簡單來說就是經過一系列的計算步驟，達到輸入與預期輸出之間的關系，

那么資料結構有多重要？我們不從學校考試、績點等方面來分析，這樣顯得格局太小且沒有意義，我們從個人的作業中來說，資料結構在校招、筆面試是必考的環節，它體現著一個人的演算法功底以及發展潛力，在日后的作業中，不會用資料結構，那....只能說...可能比較慘，（不排除個例，如果你不信的話你可以去吃個螃蟹哈~~~）（可以參見《大話資料結構》中作者舉的例子）

所以說，資料結構與演算法是一門極其極其重要的課程！！！

好，我們正式進入第一章的學習

——演算法的時空復雜度

對于很多學校和老師來說，這一節是直接不講的，

但我想說，這一節，正是演算法的核心，

甚至于比我們后面所有學的資料結構以及演算法的知識都要重要，

它對于我們代碼的優化、代碼的規范和簡化、代碼的書寫習慣都提升了一個更高的要求，

它往往體現在一些看似“微不足道”的地方，

但是，當一個專案有幾萬行、幾百萬行代碼的時候，就會被無限放大，

可以想象，

一種演算法for回圈套著for回圈又套裝for回圈，另外的一種幾句話搞定，

一種演算法是要2^n次，而另外一種演算法只要處理logn次（注：我們本章所有的log均指以2為底），當n趨向于無窮時，二者所需的時間可謂千差萬別，

我們本章暫時先不探討代碼風格，就只談演算法的優化和簡化，

我們先來說說什么叫演算法的復雜度，

演算法的復雜度包含演算法的時間復雜度和演算法的空間復雜度，我們將分別詳細地探討這兩個概念，

先打個預防針，這一節其實概念性的東西比較多，實操性比較弱，但我們從下一節順序表開始，將會在教大家思路的同時，教會大家代碼的實作，

我們目前的資料結構用的是C語言來實作，

演算法效率

演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，

時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，

空間復雜度主要衡量一個演算法所需要的額外空間，

在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，

但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，

所以我們如今已經不需要再特別關注一個演算法的空間復雜度，

演算法的特性

這里我們簡單提一下：

1.輸入：在演算法中可以有零個或者多個輸入

2.輸出：在演算法中至少有一個或者多個輸出

3.有窮性：在執行有限的步驟之后，自動結束不會出現無限回圈并且每一個步驟在可接受的時間內完成

4.確定性：演算法的每一個步驟都具有確定的含義，不會出現二義性

5.可行性：演算法的每一步都必須是可行的，也就是說，每一步都能夠通過執行有限的次數完成

演算法的時間復雜度

在理解這個概念之前，我們需要知道，什么叫做好的演算法？

我們還記得計算斐波那契數列的時候所用的演算法么？

我們當時是怎么做的？

大概率，我們是用下面的代碼實作的：

代碼運行起來之后，當我們輸入10,20,30等小數字的時候，答案確實會一下子就出來了，

但是，當我們輸入50的時候，它遲遲不出結果（下圖視頻以三倍速播放）：

有興趣的小伙伴可以試一下，應該是要十幾分鐘就能出來了😀

（這個圖gif太不清楚了~~~~555）

為什么會這樣？原因在于它的演算法的效率，真的是太太太太太低了，演算法的時間復雜度巨高，學完本章，你就能更深層次地理解這其中的原因了，

接下來，我們就要來了解一下，什么叫做演算法的時間復雜度或者說時間效率？

（圖）

（源自百度百科）

從字面意思去理解的話，實際上就是計算演算法的運算效率的函式，它也就是這個意思，

說是時間復雜度，但是我們不可能去真的計算每個程式每一次運行的時間，

因為每一次運行的時間不僅僅與你設計的代碼有關，還與你的電腦的性能、電腦當前的CPU運行的速度等等都有關系，所以，計算每一次運行的時間，意義就不大了，

那我們算什么？

實際上，我們比較的，可以認為是演算法程序中的大頭，主要矛盾，

我們用大O漸進表示法來表示，

至于大O漸進法到底是什么？

我們回到概念上去，我們剛剛說演算法的時間復雜度是計算演算法的運算效率的函式，

假設，我們用f(n)來表示一個程式要執行的陳述句次數，n可以先理解為函式f的規模，那么我們將會得到f(n)關于規模n的一個函式，

我們不要光干講概念，來舉個例子吧：

在數學中，我們如果有這么一個運算式：

F（n）=n*n + n + 5，

當n取100時，n*n為10000，而后面的只有105，105相較于10000而言，非常的小，如果n再大，那么n*n的值比n+5大的更多，n+5會相較于n*n而言會更小，小到可以忽略不計，那么n如果還要再大，后面的n+5就會更更小……

所以決定F（n)的階數的是前面的n*n，后面的n+5在n很大的時候，相較于n*n，對于結果的影響便會微不足道，

我們對于這樣的F(n)，取能主要影響結果的那一項，即n^2(n*n)，那么用大O進階表示法的話就是O(n^2)，

同樣的道理，我們可以再舉一個例子：

F(n) = 1/2*n + 5; 這里影響最終結果的一項（或者可以直接理解為次數最高的一項）為1/2*n，然后將前面的系數變成1（因為我們只抓”主要矛盾、關鍵部分“），最終，得到的大O階為O（n），

那如果F(n) = 5呢？對于常數函式，我們就用O(1)來表示，

那么我們總結一下：

大O符號（Big O notation）：

是用于描述函式漸進行為的數學符號，

推導大O階方法：

1、用常數1取代運行時間中的所有加法常數，

2、在修改后的運行次數函式中，只保留最高階項，

3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，

好，我們再用具體的代碼來舉例，

請看：（例1：）

我如果呼叫這么一個函式，請問它的時間復雜度是多少？（用大O表示）

首先，應當將其運算式寫出來，

它的運算式可以表示為：f(n) = 1+n*n+n+2n，整理一下，得：f(n)=n^2+3n+1，

所以，得到它的時間復雜度為O(N^2)，

我們再來看幾個例子：

（例二：）

請問，這個函式的時間復雜度是多少？

同樣的道理，我們還是先寫出運算式：f(n,m)=n+m+1;1相對于m和n對運算式的影響很小，所以可以忽略不計，而由于我們并不知道m與n之間的關系，所以我們應當予以保留，即該函式的時間復雜度為O(m+n)

例三：

我們再來看一個例子：

請問這個演算法的時間復雜度是多少？

還是先算運算式：f(n)=1+100+1=102; 常數階，所以為O(1)；

例四：（作用是在一個字串中找到我們想要的元素）

假如我們傳入的str為一個字串，字串的長度為n，那么請問該函式的時間復雜度為多少？

其實，這樣的情況分為很多種，換句話說，看運氣，

如果運氣好，我們一次就能找到，

如果運氣不好，要遍歷完才能判斷能否找到，就是說要到第n個才能找到（或找不到），

還可以是平均的情況，就是n/2次，

那么我們算這個函式的復雜度應該怎么弄呢？實際上，我們在算復雜度的時候，是按照最壞的情況算的，最壞情況運行時間是一種保證，那就是運行時間將不會再壞了，在應用中也是一種需求，這是一種確定的情況，所以我們在一般沒有特殊說明的情況下，都是按照最壞的情況來算，

所以，上述的演算法的時間復雜度為O(n)

例五：

請問該冒泡排序演算法的時間復雜度是多少？

我們還是把運算式寫出來：

f(n)=(n-1)+(n-2)+(n-3)+(n-4)+...+1=n*(n-1)/2

所以，它的演算法的時間復雜度應當是O(n^2)

例六：

該二分查找的演算法的時間復雜度是多少？

同樣，還要分最好和最壞的情況來討論：

最好的情況：一次就找到，那就是O(1);

最壞的情況：最后一次才找到，假設找了x次，有n個元素，則n/2/2/2/2.../2=1，那么/2這個運算進行了x次，所以n = 2^x，所以x = logn，

因此，該二分查找的演算法的復雜度為（logn）

例七：

請問該演算法的復雜度為多少？

對于遞回的演算法復雜度，它等于 遞回次數*每次遞回函式中的次數

那么對于這個例子，它遞回了多少次？

Fac(N)->Fac(N-1)->Fac(N-2)->Fac(N-3)->Fac(N-4).....->Fac(1) 遞回了n次，

故f（n) = 1*n

所以演算法復雜度為O(n)

例八：

我們回到當初的那個例子，來看看它的演算法復雜度是多少，

實際上，它的次數是一個完全二叉樹的形式（我們后面會講），那么它要算的次數就是完全二叉樹的節點的個數，所以它要運算的次數為f(n) = 2^(n-1) - 1 -X(X為完全二叉樹與同等深度的滿二叉樹的節點的個數之差，一個常數），這個我們后面也會講，

所以，它的時間復雜度為O(2^n)，

所以，我們剛剛在算50的斐波那契數列時，可想而知，得到的數字將會是一個天文數字~~~~~

關于演算法的時間復雜度，我們就先說到這里，

下面，我們再來說說演算法的空間復雜度

演算法的空間復雜度

類比于時間復雜度，對于演算法的空間復雜度，我們也不會去計算每個演算法都開辟了多少位元組的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，

空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法，

我們還是通過舉幾個例子來說明：

例一：

還是來看剛剛的冒泡排序：

請問，它的空間復雜度是多少？

實際上，它創建的變數就一個exchange，就是說，它的變數的數量是一個常數階，

所以，它的空間復雜度為O(1)

例二：

來看這么個斐波那契數列的演算法，

我們可以看出，我們用malloc創建了n+1個變數，

所以，它的空間復雜度為O(n)

例三：

來看這個階乘，

它遞回呼叫了n次，

我們在C語言的函式部分介紹過，函式的每一次遞回呼叫都會為新的函式重新開辟一個堆疊幀，上一級的函式由于并未結束，所以上一級的函式的堆疊幀并未被銷毀，所以在呼叫下一級的函式的時候，就不得不在新的位置重新為其開辟堆疊幀，

所以，它的空間可以理解為開辟了n次，

所以，它的空間復雜度為O(n)，

關于演算法的時空復雜度，對于優化代碼演算法是十分重要的，不過理解起來并沒有那么困難，希望讀者在理解上述的例題及概念后，可以去牛客網和Leetcode上找一些相應的oj題來練一練，

好啦，有關演算法的時空復雜度，我們就探討到這里啦，

歡迎關注我@jxwd，我將會在將來的2-3個月，持續推出有關資料結構與演算法、C++的知識章節，以饗讀者，

如果覺著不錯，那就不要吝嗇你的小手，點個贊吧~~😀