數(shù)據(jù)結(jié)構(gòu)和算法關(guān)系

雖然這個標(biāo)題起的叫數(shù)據(jù)結(jié)構(gòu)，但是我卻總結(jié)算法。。。我不是沒事找抽，只是呢，在學(xué)數(shù)據(jù)結(jié)構(gòu)的時候，算法是你肯定離不開的東西。

你平時在網(wǎng)上看到的那些文章，在你不經(jīng)意間搜的時候，是不是都是搜的數(shù)據(jù)結(jié)構(gòu)與算法這七個字。這說明啥，這說明他們倆是離不開的。

給你打個比方，你想看德云社相聲（我也想看），有一天你最想看小岳岳專場，想看小白專場。但是呢，走到園子里之后發(fā)現(xiàn)，他們今天生病了，換成了另一批人，你開心嗎，不開心對不對。

所以，數(shù)據(jù)結(jié)構(gòu)和算法也是這樣的。沒有其中的任何一個都不行。

但是，根據(jù)大學(xué)里邊的概念性的東西來說，類似于我們學(xué)校，算法是單獨開設(shè)課程，并不是和數(shù)據(jù)結(jié)構(gòu)一起。所以，這一章還是理論。

高斯求和

想必看到這兒的人肯定對這個人早有耳聞。
如果讓你來做累加求和，你肯定會寫這樣的代碼：

int sum=0;
int n=100;
for(int i=0;i<=n;i++){
sum+=i;
}

這樣做確實沒錯，但是問題來了，你這和循環(huán)了多少次？如果沒寫錯的話，是101次吧。為什么呢，因為你在每次累加的時候都會去走一遍for循環(huán)，這樣就會平平增加不必要的時間去運算，你有這時間，你根本就搶不到亞索。

我們直接來看這個天才當(dāng)時是怎么做的。

因為sum=1+2+3+…+100。

但是呢，sum=100+99+98+…+1

如果把他們兩個加起來，那就是2sum=101+101+101+…+101

一共多少個101，100個吧，那如果去除2呢，結(jié)果不就是5050了。用代碼怎么寫？

int i=0;
int sum=0
int n=100;
sum=(1+n)*n/2

這就是神童，這就是大佬，思考問題的方面都和我們不一樣。

也就是說，用這種方式，我們省略掉了那100次多余的運算，只需要一次運算就能得出答案。

如果讓你加到一億呢？你想想哪種效率會更高。

算法定義

算法這個詞最早是提出在公元825年的一個叫阿勒·花剌子的一個波斯數(shù)學(xué)家寫的《印度數(shù)字算術(shù)》里面。

目前來說，普遍的定義就是：

算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或者多個操作

剛才的問題我們也看了，對于一個問題可以有多個方法解除答案。那么問題來了，有木有通用的算法？
這個答案其實就和你去醫(yī)院買藥一樣，請問有沒有能治所有病的藥答案一樣。

算法的特性

算法具有五個特性：輸入、輸出、有限、確定、可行

輸入輸出

這個比較好理解。算法具有零個或者多個輸入。

有窮性

指的是算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)，并且每一個步驟在可接受的時間內(nèi)完成。
當(dāng)然，這里的有窮指的是在實際意義中合理的。

可行性

算法的每一步都是必須可行的，也就是說，每一步都能通過執(zhí)行有限次數(shù)完成。

算法設(shè)計的要求

剛才我們說過，算法并不是唯一的。那我們在處理一個問題的時候，就必須要事先設(shè)計好算法才去解決問題。

正確性

算法的正確性是指算法至少應(yīng)該具有輸入和輸出和加工廠處理無歧義性、能正確反映問題的需求、能狗得到問題得正確答案。

可讀性

算法設(shè)計的另一目的就是為了方便閱讀，理解和交流

你說你寫一個很牛逼的代碼，別人看不懂，，，怎么去承認(rèn)你牛逼呢是不是

健壯性

當(dāng)輸入數(shù)據(jù)不合法時，算法也能做出相應(yīng)的處理，而不是產(chǎn)生異?；蛘吣婷畹慕Y(jié)果

時間效率高和存儲量低

算法設(shè)計應(yīng)該盡量滿足時間效率高和存儲量低的特點

這一點我遲遲沒有達(dá)到。。。。

算法效率的度量方法

算法的效率指的就是算法的執(zhí)行時間。那我們怎么去算一個他的執(zhí)行時間呢？

最簡單的方法其實就是用計算機的計時功能來計算不同算法的效率是高是低。

事后統(tǒng)計法

通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而確定算法效率的高低

但是這種方法有很大的缺陷。

事前分析估算方法

在計算機程序編制前，依據(jù)統(tǒng)計方法對算法進行估算

經(jīng)過分析發(fā)現(xiàn)，一個用高級程序語言編寫的程序在計算機上運行時所消耗的時間取決于這些：

1. 算法采用的策略、方法
2. 編譯產(chǎn)生的代碼質(zhì)量
3. 問題的輸入規(guī)模
4. 機器執(zhí)行指令的速度

其實你想想，這上面四條哪一條最重要？無非就是問題的輸入規(guī)模。

所謂的輸入規(guī)模就是輸入量的大??；

我們再分析一下剛才的高斯求和；

第一種：

int sum=0; // 執(zhí)行了1次
int n=100; // 執(zhí)行了一次
for(int i=0;i<=n;i++){ // 執(zhí)行了n+1次
sum+=i; // 執(zhí)行了n次
}

第二種：

int sum=0; // 執(zhí)行了一次
int n=100; // 執(zhí)行了1次
sum=(1+n)*n/2; // 執(zhí)行了1次

孰優(yōu)孰劣，這下看得出來吧；

我們再看一個衍生算法：

int i;
int j;
int x=0;
int sum=0;
int n=100;
for(i=1;i<=n;i++){
	for(j=1;j<=n;j++){
		x++;
		sum+=x;
	}
}

這個例子很好理解，其實也就是多循環(huán)了一百次而已，那么最后算出的次數(shù)是多少呢？n²，沒錯吧

我們不關(guān)心程序用的什么語言，在什么機器上執(zhí)行，只關(guān)心算法。最終在分析程序的運行時間時，最重要的是把程序堪稱是獨立于程序設(shè)計的算法或一系列步驟。

可以從問題中得到啟示，同樣的規(guī)模，都是輸入n，求和算法的不同，使得這個運行效率也是不同；

第一種總結(jié)出來就是f(n)=n；

第二種簡單了，就是f(n)=1；第三種呢？f(n)=n²

用一張圖展示一下？（來源于網(wǎng)絡(luò)）

函數(shù)的漸進增長

我們現(xiàn)在來舉個例子，兩個算法a和b哪個更好。假設(shè)兩個算法的輸入規(guī)模都是n，算法a要做2n+3次操作（兩次n循環(huán)，3次運算），算法b做3n+1次操作。

用一張表來演示一下：

看這張表，最后我們總結(jié)出算法a總體來說優(yōu)于算法b

輸入規(guī)模n在沒有限制的情況下，只要超過一個數(shù)n，這個函數(shù)就總是大于另一個函數(shù)，我們稱為是漸進增長

函數(shù)的漸進增長：給定兩個函數(shù)f(n)和g(n)，如果存在一個整數(shù)N使得隊醫(yī)所有的n>N，f(n)總是比g(n)大，那么我們說f(n)的漸進增長快于g(n)

從中我們發(fā)現(xiàn)，隨著n的增大，后面的+3還是+1其實不怎么影響最終的結(jié)果，所以我們可以去忽略這些常數(shù)。我們再看看第二個例子：

當(dāng)n<=3的時候，算法c要差于算法d，但是當(dāng)n>3之后，優(yōu)勢就開始出來了。

所以最后總結(jié)出，與最高次項的常數(shù)并不重要。

其實根據(jù)這兩個表，大致都能分析出來，某個算法，隨著n的增大，他會越來越優(yōu)于另一種算法，或者越來越差于另一種算法

這其實就是事前估算方法的理論依據(jù)，通過算法時間復(fù)雜度來估算時間效率

算法時間復(fù)雜度

定義：在進行算法分析時，語句的執(zhí)行次數(shù)T（n）是關(guān)于問題規(guī)模n的函數(shù)，進而分析T（n）隨n的變化情況而確定T（n）的數(shù)量級。算法的時間復(fù)雜度，也就是算法的時間量度，記作：T（n）=O(f(n))。他表示隨著問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f（n）的增長率相同，稱作算法的漸進時間復(fù)雜度，簡稱為時間復(fù)雜度。其中f（n）是問題規(guī)模n的某個函數(shù)；

總結(jié)

本篇文章就到這里了，希望能給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評論