數(shù)據(jù)結(jié)構(gòu)與算法

終于開始搞這塊難啃的骨頭了，走上這條漫漫長(zhǎng)路之前要明白：

什么是數(shù)據(jù)結(jié)構(gòu)？什么是算法？

是數(shù)據(jù)之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，為編寫出一個(gè)“好”的程序，必須分析待處理對(duì)象的特性及各處理對(duì)象之間存在的關(guān)系，這也就是研究數(shù)據(jù)結(jié)構(gòu)的意義所在為編寫出一個(gè)“好”的程序，必須分析待處理對(duì)象的特性及各處理對(duì)象之間存在的關(guān)系這也就是研究數(shù)據(jù)結(jié)構(gòu)的意義所在

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

拋開上面的學(xué)術(shù)性口水話，簡(jiǎn)單來說就是:

1.數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)，組織數(shù)據(jù)的方式

2.算法是一系列規(guī)定的計(jì)算步驟，為了實(shí)現(xiàn)的特定的計(jì)算目的而應(yīng)用

給個(gè)更直觀的視圖就是：算法+數(shù)據(jù)結(jié)構(gòu)就等于程序，數(shù)據(jù)結(jié)構(gòu)可以理解為實(shí)現(xiàn)一個(gè)程序的基本單位，算法可以看作一個(gè)加工過程。

比如我去從一個(gè)很大的數(shù)組里面提取某個(gè)特定的對(duì)象，我們既可以老老實(shí)實(shí)從頭到尾遍歷查找，也就是所謂的暴力搜索，工程量隨著數(shù)組的容量增大而增大；我們也可以巧奪智取，用二分查找讓我們工作事半功倍。

分析維度

在知道基本概念后，我們說在拿到一個(gè)算法后，我們?cè)趺慈タ此暮脡模炕蛘呓o你多個(gè)算法，他們都實(shí)現(xiàn)同一個(gè)功能，我們?cè)趺慈ヅ袛嗨膬?yōu)缺點(diǎn)去取舍呢？正常情況下，我們會(huì)選擇把這個(gè)代碼放在某個(gè)環(huán)境下運(yùn)行比較時(shí)間，但這個(gè)做法有一個(gè)致命的缺點(diǎn)，在我們不同機(jī)器上，會(huì)有不同的結(jié)果，在好的機(jī)器上，運(yùn)行時(shí)間會(huì)很短，但是在比較差一點(diǎn)的主機(jī)上，就稍有遜色，這樣一來就有失公平。

大O的漸進(jìn)表示法

不要直接計(jì)算時(shí)間，，我們需要去計(jì)算一個(gè)漸進(jìn)的時(shí)間復(fù)雜度，也就是所謂的Big O （大O表示法），他其實(shí)本質(zhì)上實(shí)在求一個(gè)量級(jí)（時(shí)間）在增加時(shí)的一個(gè)變化趨勢(shì)

時(shí)間復(fù)雜度公式：T（n）=O(f(n))

T（n）：時(shí)間頻度（執(zhí)行次數(shù)）
n ：?jiǎn)栴}規(guī)模；
f（n）：T(n)的同數(shù)量級(jí)函數(shù)；
O ：代表正比例關(guān)系；
Ｏ(f(n)）：即算法的漸進(jìn)時(shí)間復(fù)雜度

常數(shù)階

我們的算加法的完整過程：

int main()
{
int a = 1;
int b = 1;
int sum = a+b;
printf("%d",sum);
}

我們每走一步就會(huì)執(zhí)行一次，上面的代碼我就執(zhí)行了四次；那么如果我把他的sum部分重復(fù)執(zhí)行數(shù)十次數(shù)百次數(shù)千次，但他本質(zhì)上和執(zhí)行四次沒有區(qū)別，執(zhí)行時(shí)間是恒定的，這個(gè)層面上，他的時(shí)間復(fù)雜度就是O（1）（常數(shù)階）。

不管這個(gè)常數(shù)是多少，4或∞，都不能寫成O(4)、O(∞)，都要寫成O(1)

線性階

我們給出一個(gè) for loop

for(int a = 1;a<=n;a++)
{
 a++;
}

分析線性階時(shí)會(huì)比常數(shù)階更復(fù)雜因?yàn)橐治鏊难h(huán)結(jié)構(gòu)，上面的代碼限制再++，總共執(zhí)行3次，包括常數(shù)階的賦值就是O（3n+1），在我的n足夠大時(shí)他會(huì)無限接近于無窮，這時(shí)的+1就會(huì)沒有意義。

這時(shí)就順理成章，嵌套循環(huán)我們也就可以理解了，兩層 for 就是O（n2)，三層就是O（n2）for 下面加一個(gè)雙層for循環(huán)就是O（n+n2）……這里面就包含了**平方階**；此時(shí)我O(n)的效率就比O（n2）高。

對(duì)數(shù)階

我們?cè)俳o出一個(gè)while loop

int n = 0;
while(n<100000)
{
n*=2;
}

我們要看執(zhí)行次數(shù)就要看多少步才能走出循環(huán)，就意味著要乘 x 個(gè)2能>=10000，則表示為 2^x =100000，假設(shè)為隨機(jī)數(shù) a，則 x= log 2 ^a，
復(fù)雜度為O（logn）

除了上面三種之外還有其他的復(fù)雜度

從常數(shù)階到階乘是越來越復(fù)雜，我們看一下直觀數(shù)據(jù)：

這里橫軸是輸入（input）量級(jí)，縱軸是消耗時(shí)間也就是時(shí)間復(fù)雜度，也就是有個(gè)很直觀的信息：算法復(fù)雜度越高，需要的時(shí)間越長(zhǎng)，到后面就直接指數(shù)級(jí)增長(zhǎng)。

其他時(shí)間復(fù)雜度指標(biāo)

雖然有下面這些種吧，但我們主要會(huì)把重心放在 O 上，畢竟它是最常用的指標(biāo)。

空間復(fù)雜度

空間復(fù)雜度是指內(nèi)存空間增長(zhǎng)的趨勢(shì)，相對(duì)就容易理解一些，O（1）就是相當(dāng)于單次賦值，而 O（n）相當(dāng)于賦值n次，可以把他想成一個(gè)大小為 n 的數(shù)組，復(fù)雜度越高需要分配的空間就越多；同理，O（n^2）就可以想成一個(gè)n行n列的二維數(shù)組。

今天就到這里吧，摸了家人們，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法時(shí)間空間復(fù)雜度的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論