乾貨 | 數據結構與演算法 – 什麼是演算法
- 2020 年 2 月 25 日
- 筆記
文案 向柯瑋 排版 鄧發珩
疫情尚未結束，今天繼續加油！在家好好學習，好好充實自己，祝大家身體健康。
前言
大家好呀， 我是小瑋~今天給大家帶來的是學習筆記之數據結構與演算法–什麼是演算法。
說到演算法呀，我相信每個學過編程的人都或多或少接觸到過。但是可能呢，你並不了解一個演算法的定義是什麼，演算法好壞如何判斷，演算法和數據結構的關係，等等。讓我們帶著我們的疑問，慢慢地去走進演算法，去了解它。
本次學習筆記的主要內容有：數據結構和演算法的關係，演算法的定義，演算法的特性，演算法設計的要求，演算法效率的度量方法，時間複雜度與空間複雜度。
數據結構與演算法
其實現在市面上關於數據結構的書的名字，一般都不是單單以數據結構為名，它通常是以數據結構與演算法為名，比如怎麼學好數據結構與演算法。其實在演算法導論中，也是把數據結構和演算法一塊講的。
那麼為什麼他們總是在一塊呢？我們可以舉一個例子來說。你把房子的基礎打好了，但是你沒有想好上面應該怎麼修，那房子還修不修？同理，你把上面怎麼修想好了，基礎卻不知道怎麼辦，那房子還修不修？
再舉一個例子，你要去看話劇，發現話劇名字叫做《羅密歐》，很奇怪，就去問前台這是怎麼回事，前台解釋說，女主角生病了，演不了了，只有男主角了，所以這部話劇改為講男主角的心路歷程。那話劇還看得下去嗎？
沒錯，數據結構和演算法的關係也是類似，只學數據結構，你會感覺自己什麼都沒有學到，只學演算法，你會總感覺不能很完整。
演算法的定義
其實演算法就是描述解決問題的方法，它最早是花拉子米提出來的，沒錯就是咱們數學書上面的花拉子米。從中可以看出，編程果然是與數學有著密不可分的關係啊。
在現代，最普遍認可的演算法的定義是：演算法是解決特定問題求解步驟的描述，在電腦中表現為指令的有限序列，並且每條指令表示一個或多個操作。
其實這個也很好理解，就是為了解決某個問題，把一些指令按照順序排起來，完成一些操作，這就是演算法。
演算法的特性
說到演算法的特徵，一般來說公認的有五大基本特徵，即：輸入，輸出，有窮性，確定性和可行性。
輸入：這個其實相對來說很容易理解，一個演算法可以有零個或者多個輸入，比如說，我們第一次學編程的時候，我們做的第一個演算法是什麼？沒錯，就是輸出『hello world』，這個就不需要咱們輸入參數，但是絕大多數演算法都是需要我們輸入一些參數進去的。
輸出：一個演算法最起碼會有一個或者多個輸出，如果你的演算法沒有輸出，你設計它幹什麼呢？
有窮性：它在嚴格意義上來講，並不僅僅是數學意義上無窮的對立，它是指程式在人們可以接受的時間範圍內完成，如果一個程式陷入了無限循環，或者一個演算法需要運算幾十年，那都算無窮，那都是沒有意義的演算法。
確定性：這個也非常容易理解，演算法的每一個步驟都具有確定的意義，不會出現多重含義，演算法在一定的條件下，只能有一條執行路徑。一旦出現了歧義，那麼編譯器就會報錯，我相信這一點大家都理解吧？
可行性：演算法的每一步都必須是可執行的，也就是說，每一步都能夠通過執行有限次數完成。這一點，我感覺有有窮性有異曲同工之處。
演算法設計的要求
我們都知道，想要實現某種目的，我們可以設計多種多樣的演算法去實現，但是一個好的演算法，他一般都滿足以下的特點。
正確性：它的意思是，演算法至少應該具有輸入,輸出和加工處理無歧義，能正確反映問題的需求，能夠得到問題的正確答案。它主要包括四個層次：1、沒有語法錯誤。2、對於合法的輸入，能夠給出滿足要求的輸出。3、對於錯誤的輸入，能夠給出相應規格提示的輸出。4、對於各種刁難的輸入，也能給出滿足要求的輸出。
可讀性：它的意思是，演算法設計的另一目的是為了便於閱讀，理解和交流。對於一個優秀的演算法而言，它不僅僅要求是解決這個問題，它還要求別人能夠理解，這樣也有利於演算法問題的發現以及改進，同時更是方便自己以後回來再看的時候能夠明白。
在這裡我想到了一個例子，前段時間有很多有用最少程式碼完成xxx的挑戰，很多大神確實用了很少很少的程式碼，完成了這些挑戰，但是程式碼最終公布出來，很少人能夠明白其中的意思，這樣的程式碼就不屬於好的程式碼。
健壯性：它的意思是，能夠對錯誤的數據進行正確的相應處理，而不是輸出一些稀奇古怪的東西。舉個例子來說，你設計了一款根據路程求時間的演算法，他們輸入了一個負數進來，你的演算法應該能夠給出相應的回復，而不是異常的回復。
時間效率高並且儲存量低：這個其實就是評判演算法好壞最關鍵的一點，也是從事優化演算法行業的人最高的追求。就和人們在現實生活中一樣，我們總是想用最少的投入，獲得最大的收益。那麼一款優質的演算法也是一樣，它講究用最快的時間，最少的空間，去完成最多的任務。
演算法效率的度量方法
對於一個演算法的效率，我們應該怎麼度量呢？它主要分為兩種：事後統計方法和事前分析估算方法。
事後統計方法：這種方法主要是通過設計好程式以後的測試程式和數據，利用計算器對不同演算法編製的程式的運行時間進行比較，從而判斷演算法的效率。這種方法的缺陷很明顯。我覺得主要有以下幾點：
>有可能導致花費了大量時間去寫一個程式，最後運行了發現是一個很糟心的程式 。
>比較的方式有誤，運行時間不僅僅是取決於演算法的好壞，同時也取決於電腦配置的好壞，你用同樣的演算法在最先一代電腦上運行和在現在最旗艦的電腦上運行，效果肯定存在巨大差異。
>測試數據存在選擇問題，你不知道自己的演算法應該選取多大的數據，就那排序演算法來說，幾個數字的排序，無論哪一種演算法，其實都差不多，只有當數據非常大的時候才會有明顯差異。
事前估算分析方法：它的意思是，在編譯之前，就依據統計方法對演算法進行估算。那麼這個估算主要是在哪些方面呢？
>演算法採用的策略，方法。
>編譯產生的程式碼品質。
>問題的輸入規模。
>機器執行指令的速度。
第一條當然是演算法好壞的根本，第二條是由編譯器決定的，第四條需要看電腦的性能，也就是說，不考慮軟體和硬體，一個程式的運行時間其實是取決於演算法的好壞和問題的輸入規模（即輸入量的多少）。
下面我們舉一個例子來說明一下。等差數列求和，大家肯定都知道吧？那麼針對這個問題，我們可以設計兩種最常規的演算法。
1: cin>>n; int i,sum=0; for(i=1;i<=n;i++) sum+=i; cout<<sum; 2: cin>>n; int sum=0; sum=(1+n)*n/2 cout<<sum;
在這兩種演算法中，雖然我們輸入的是一樣的，但是內部的計算過程是完全不在一個等級的，這就是1與n的差距。對吧？
我們在分析程式時間的時候，就應該把程式當成是獨立於程式語言一系列步驟，我們把其中的基本操作的數量和輸入規模聯繫起來。
就拿上面的例子來說，對於同樣的輸入規模n，方法一需要運n^2次，而方法二隻需要運行n次。這就是一個質的飛躍。
時間複雜度與空間複雜度
說到這兩個概念，雖然在書上看到很多相關的內容但是我覺得我們只需要關注兩個方面，即：它們的意思是什麼，它們怎麼推導。
時間複雜度：我們通常用O（x）來表示時間複雜度，它的意思是在最壞的條件下，這個程式會運行多少次。打個比方來說，我們現在用冒泡排序對面下面的數組進行排序。
我們只需要運行一次就可以完成我們的目的，但是如果是下面這個數組呢？
是不是相應的，程式運行次數就更複雜了？那麼最壞的情況是什麼樣的呢？
沒錯，就是這種情況，那麼這種情況下，程式會運行多少次？是8^2=64次吧？那麼依據我們的定義，冒泡排序的時間複雜度就是O（n^2）。
我們通常將推導時間複雜度的過程叫做，推導大O階，那麼就可以知道，我們把上面出現的n^2，稱為平方階，把n稱為線性階，那麼，現在我們來思考一下，如果是lg(n)呢？沒錯，就是對數階了。
在推導的過程當中，我們應該注意的是：
>如果這個n為一個常數，我們統一認為時間複雜度是O(1)。
>如果n的前面存在係數，我們統一認為時間複雜度是O(n)，即把前面的係數當成1處理。
>如果最終算出時間複雜度為O(n^2+n-i)的類似形式，我們只保留最高階。
空間複雜度 ：既然已經有了時間複雜度的基礎，那麼空間複雜度也就不難理解了。而且如果出現了複雜度，在通常情況下，都是指的時間複雜度。
我在這裡就不多加介紹空間複雜度了。我們直接寫出空間複雜度的表示方法。S(n)=O（f（n）），這裡n是問題的規模，f（n）是關於n所佔儲存空間的函數。
到這個位置為止，我們基本上已經完全了解了數據結構和演算法的一些基本內容。在之後的推文中，我們就正式進入數據結構與演算法的主體內容了。
希望各位看客老爺能夠認真地讀好前兩篇推文，這是一個非常重要的基礎部分。那麼，我們下期再見啦~
