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

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

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

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

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

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

高斯求和

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

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

這樣做確實(shí)沒錯(cuò)，但是問題來了，你這和循環(huán)了多少次？如果沒寫錯(cuò)的話，是101次吧。為什么呢，因?yàn)槟阍诿看卫奂拥臅r(shí)候都會(huì)去走一遍for循環(huán)，這樣就會(huì)平平增加不必要的時(shí)間去運(yùn)算，你有這時(shí)間，你根本就搶不到亞索。

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

因?yàn)閟um=1+2+3+…+100。

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

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

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

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

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

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

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

算法定義

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

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

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

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

算法的特性

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

輸入輸出

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

有窮性

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

可行性

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

算法設(shè)計(jì)的要求

剛才我們說過，算法并不是唯一的。那我們?cè)谔幚硪粋€(gè)問題的時(shí)候，就必須要事先設(shè)計(jì)好算法才去解決問題。

正確性

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

可讀性

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

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

健壯性

當(dāng)輸入數(shù)據(jù)不合法時(shí)，算法也能做出相應(yīng)的處理，而不是產(chǎn)生異常或者莫名奇妙的結(jié)果

時(shí)間效率高和存儲(chǔ)量低

算法設(shè)計(jì)應(yīng)該盡量滿足時(shí)間效率高和存儲(chǔ)量低的特點(diǎn)

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

算法效率的度量方法

算法的效率指的就是算法的執(zhí)行時(shí)間。那我們?cè)趺慈ニ阋粋€(gè)他的執(zhí)行時(shí)間呢？

最簡單的方法其實(shí)就是用計(jì)算機(jī)的計(jì)時(shí)功能來計(jì)算不同算法的效率是高是低。

事后統(tǒng)計(jì)法

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

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

事前分析估算方法

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

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

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

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

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

我們?cè)俜治鲆幌聞偛诺母咚骨蠛停?br />

第一種：

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)孰劣，這下看得出來吧；

我們?cè)倏匆粋€(gè)衍生算法：

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;
	}
}

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

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

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

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

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

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

函數(shù)的漸進(jìn)增長

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

用一張表來演示一下：

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

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

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

從中我們發(fā)現(xiàn)，隨著n的增大，后面的+3還是+1其實(shí)不怎么影響最終的結(jié)果，所以我們可以去忽略這些常數(shù)。我們?cè)倏纯吹诙€(gè)例子：

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

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

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

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

算法時(shí)間復(fù)雜度

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

總結(jié)

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

最新評(píng)論