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