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

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

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

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

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

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

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

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

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

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

分析維度

在知道基本概念后，我們說在拿到一個算法后，我們怎么去看他的好壞？或者給你多個算法，他們都實(shí)現(xiàn)同一個功能，我們怎么去判斷他的優(yōu)缺點(diǎn)去取舍呢？正常情況下，我們會選擇把這個代碼放在某個環(huán)境下運(yùn)行比較時間，但這個做法有一個致命的缺點(diǎn)，在我們不同機(jī)器上，會有不同的結(jié)果，在好的機(jī)器上，運(yùn)行時間會很短，但是在比較差一點(diǎn)的主機(jī)上，就稍有遜色，這樣一來就有失公平。

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

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

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

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

常數(shù)階

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

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

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

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

線性階

我們給出一個 for loop

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

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

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

對數(shù)階

我們再給出一個while loop

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

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

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

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

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

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

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

空間復(fù)雜度

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

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

最新評論