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