數(shù)據(jù)結(jié)構(gòu)入門介紹

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

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

如何擺放圖書館的書?

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

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

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

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

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

一個多項式求值的問題。

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

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

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

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

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

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

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

什么是算法

一個有限的指令集

接受一些輸入?？梢詻]有輸入。

產(chǎn)生輸出。

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

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

可行性。

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

什么是好的算法

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

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

1、時間復(fù)雜度

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

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

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

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

最壞情況：任意輸入最長的運行時間。

平均情況：任意輸入期待運行時間。

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

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

2、空間復(fù)雜度

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