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

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。

如何擺放圖書(shū)館的書(shū)?

擺放圖書(shū)館的書(shū)與書(shū)的規(guī)模和對(duì)書(shū)要進(jìn)行的操作有關(guān)。

也就是說(shuō)，如何確定一個(gè)問(wèn)題的數(shù)據(jù)結(jié)構(gòu)，需要考慮到問(wèn)題的規(guī)模和程序中要進(jìn)行的操作。

打印一個(gè)數(shù)列從1到N，采用遞歸和循環(huán)的方式。

遞歸方式容易理解，解決問(wèn)題效率高，但計(jì)算執(zhí)行復(fù)雜，占用空間大。循環(huán)的方式不便于理解，但計(jì)算機(jī)執(zhí)行效率高，占用內(nèi)存小。

說(shuō)明解決問(wèn)題的效率和空間占用效率有關(guān)

一個(gè)多項(xiàng)式求值的問(wèn)題。

對(duì)于一個(gè)多項(xiàng)式求值的問(wèn)題，可以采用正常的從前往后逐項(xiàng)累加，也可以使用“巧妙的結(jié)合律”，從里向外求和，從而使得乘法的次數(shù)被降低，算法執(zhí)行效率提升。

說(shuō)明了解決問(wèn)題的效率和算法的巧妙程度有關(guān)

綜上，要談?wù)撘粋€(gè)問(wèn)題采用什么數(shù)據(jù)結(jié)構(gòu)必須要明確問(wèn)題的規(guī)模和問(wèn)題的需求，這樣才能使用合適的數(shù)據(jù)結(jié)構(gòu)。我們可以使用“空間”來(lái)?yè)Q取“時(shí)間”，或者用“時(shí)間”換取“空間”。算法的巧妙程度決定了一個(gè)算法的效率。

數(shù)據(jù)組織的邏輯結(jié)構(gòu)：一對(duì)一(線性)，一對(duì)多(樹(shù))，多對(duì)多(圖)

數(shù)據(jù)結(jié)構(gòu)的抽象描述

數(shù)據(jù)對(duì)象集

在數(shù)據(jù)集上對(duì)應(yīng)的操作

什么是算法

一個(gè)有限的指令集

接受一些輸入?？梢詻](méi)有輸入。

產(chǎn)生輸出。

有窮性。一定步驟后終止。

確定性。每一步都應(yīng)該是明確的，沒(méi)有歧義。

可行性。

每一天指令應(yīng)該：正確性、可讀性、便于閱讀理解和維護(hù)。健壯性、 輸入不合法時(shí)，依然不會(huì)崩潰。

什么是好的算法

衡量一個(gè)算法的好壞，普遍會(huì)使用時(shí)間復(fù)雜度和空間復(fù)雜度。它們兩個(gè)共同決定了算法所需要消耗的資源。這些資源可能包括CPU資源，RAM資源，帶寬資源。

確定一個(gè)算法的好壞可以使用事后統(tǒng)計(jì)或者事前分析。事后統(tǒng)計(jì)就是利用設(shè)計(jì)好的數(shù)據(jù)集，在測(cè)試程序上運(yùn)行，然后統(tǒng)計(jì)各種資源的使用情況，從而分析算法的效率。事前分析就是利用統(tǒng)計(jì)的方法，對(duì)算法效率進(jìn)行估算。

1、時(shí)間復(fù)雜度

算法的時(shí)間復(fù)雜度，描述的是算法的運(yùn)行時(shí)間。實(shí)際的運(yùn)行時(shí)間其實(shí)是很難計(jì)算出來(lái)，對(duì)于不同的環(huán)境，每條語(yǔ)句的執(zhí)行時(shí)間可能都不相同。這里的描述相當(dāng)于算法中語(yǔ)句的執(zhí)行次數(shù)。

對(duì)于給定的問(wèn)題規(guī)模n，那么語(yǔ)句的執(zhí)行次數(shù)和問(wèn)題規(guī)模n之間的關(guān)系可以用T(n)來(lái)表示。通過(guò)T的大致趨勢(shì)也能反映出算法的時(shí)間耗費(fèi)，不需要給出精確地T值，所以在這個(gè)基礎(chǔ)上引出來(lái)漸進(jìn)時(shí)間復(fù)雜度。

當(dāng)問(wèn)題規(guī)模n趨向于無(wú)窮大時(shí)，算法的時(shí)間復(fù)雜度T(n)的漸進(jìn)上界，叫做漸進(jìn)時(shí)間復(fù)雜度。在實(shí)際使用中，漸進(jìn)時(shí)間復(fù)雜度和時(shí)間復(fù)雜度不予區(qū)分，記為：T(n) = O(f(n)).在實(shí)際中，O表示在最壞情況下的漸進(jìn)上界。關(guān)于漸進(jìn)符號(hào)的知識(shí)，可以參考這里。

然而，對(duì)于同一個(gè)算法，不同的數(shù)據(jù)，可能時(shí)間復(fù)雜度是不同的。所以，又分為三種情況的時(shí)間復(fù)雜度：

最壞情況：任意輸入最長(zhǎng)的運(yùn)行時(shí)間。

平均情況：任意輸入期待運(yùn)行時(shí)間。

最佳情況：對(duì)于特定輸入，最快執(zhí)行時(shí)間。

在實(shí)際中，一般使用最壞情況下的時(shí)間復(fù)雜度。

2、空間復(fù)雜度

空間復(fù)雜度用S表示。它描述的是算法執(zhí)行期間所要占用的空間。程序占用的空間一部分是和算法無(wú)關(guān)的，例如：指令，常數(shù)，輸入數(shù)據(jù)等，所以這一部分不是分析的空間。在算法執(zhí)行過(guò)程中所需要的輔助空間才是我們所關(guān)心的。