一、數(shù)據(jù)類型

定義：一組值的集合以及定義在這組值上的一系列操作。(值集 + 操作集合)

站在計算機和程序員的角度：計算機只認識 0 和 1 ，如果直接讓程序員操作0和1，想必會瘋掉一批人，所以，由編譯器 和編程語言將他們抽象成基本數(shù)據(jù)類型供廣大猿類使用。所以，通過編譯器和編程語言來確定他們在計算機中的長度和可以進行的操作。

舉例：例如Java中基本類型int占用2字節(jié)(16位)，而在變他們可以進行 " +，-，x，/“ 等操作，不可以進行并，交，差等操作。所以它的值集：-2^15 ~ 2^15-1(因為0的存在所以需要-1)，操作集合：” +，-，x，/ “ 等

分類：

• 基本數(shù)據(jù)類型
  系統(tǒng)定義的(編程語言提供的)數(shù)據(jù)類型成為基本數(shù)據(jù)類型，如Java中的int,float,double,char等。
• 用戶自定義數(shù)據(jù)類型
  用戶可以自己定義的數(shù)據(jù)類型，如Java中的類。

二、數(shù)據(jù)結(jié)構(gòu)(有關(guān)系的數(shù)據(jù) + 存在的關(guān)系)

定義：由相互之間存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合和該集合中數(shù)據(jù)元素之間的關(guān)系組成。它是存儲和組織數(shù)據(jù)的一種方式。(實質(zhì)：有關(guān)系的數(shù)據(jù)元素 + 關(guān)系集合)

三要素：(數(shù)據(jù)關(guān)系 + 數(shù)據(jù)存儲 + 數(shù)據(jù)操作)

• 數(shù)據(jù)的邏輯結(jié)構(gòu) ：反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu),主要是指他們之間的前后關(guān)系，如集合關(guān)系(前后無關(guān)系，但同屬一集合)，線性結(jié)構(gòu)(前后一對一)，樹形結(jié)構(gòu)(前后一對多)，圖形結(jié)構(gòu)(前后多對多)。
• 數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間的存放形式，也就是數(shù)據(jù)在計算機內(nèi)的表示。如順序存儲，鏈接存儲，散列存儲，索引存儲等。一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲結(jié)構(gòu)。
• 數(shù)據(jù)的運算結(jié)構(gòu)：也就是這些數(shù)據(jù)可以進行哪些運算操作。

三、數(shù)據(jù)結(jié)構(gòu) VS 數(shù)據(jù)類型 VS 抽象數(shù)據(jù)類型

數(shù)據(jù)結(jié)構(gòu)：抽象的數(shù)據(jù)對象以及該數(shù)據(jù)對象集合中的數(shù)據(jù)元素之間的相互關(guān)系。
從名字上來說，它表示的就是數(shù)據(jù)的結(jié)構(gòu)，包括構(gòu)成的成分，構(gòu)成的方式和結(jié)構(gòu)。
它反應(yīng)的數(shù)據(jù)內(nèi)部的構(gòu)成方式，常用結(jié)構(gòu)圖來表示(如結(jié)點，邊等)

數(shù)據(jù)類型：計算機程序中的數(shù)據(jù)對象以及定義在這個數(shù)據(jù)對象集合上的一組操作的總稱。
從名字上看，它表示的是數(shù)據(jù)的類型，也就是將數(shù)據(jù)按照數(shù)據(jù)結(jié)構(gòu)進行分類后，所屬的類型。即同一類數(shù)據(jù)的所有稱為一個數(shù)據(jù)類型。它最早出現(xiàn)在高級程序語言中，用戶來刻畫操作對象的特征，按照“值”的不同，可以分為非結(jié)構(gòu)的原子數(shù)據(jù)類型和結(jié)構(gòu)類型。
所以,一類數(shù)據(jù)結(jié)構(gòu)對應(yīng)著一種數(shù)據(jù)類型。

抽象數(shù)據(jù)類型ADT：一個數(shù)學(xué)模型以及定義在該模型上的一組操作。它與具體在計算機內(nèi)部如何實現(xiàn)的無關(guān)，即只要它的數(shù)字特性不變，不管內(nèi)部實現(xiàn)如何，它都不影響外部使用(類似面向?qū)ο蟮姆庋b思想)。
抽象數(shù)據(jù)類型和數(shù)據(jù)類型實際上是一個概念，它可以理解為數(shù)據(jù)類型的進一步抽象，即將數(shù)據(jù)類型和數(shù)據(jù)類型上的運算捆綁在一起進行封裝，這樣我們可以自定義一些不同的數(shù)據(jù)結(jié)構(gòu)，如：類結(jié)構(gòu)等。只是原子類型已經(jīng)由編程語言為使用者已經(jīng)實現(xiàn)了而已。

四、算法

定義：指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制。

特征：

• 有窮性：執(zhí)行步驟又窮
• 確切性：每一步都是確切的，不具備二義的；
• 輸入輸出：算法有0-n個輸入和1-n個輸出；
• 可行性：算法是可行的，不是憑空想象不切實際的。

衡量標(biāo)準(zhǔn)：評價一個算法的好壞的標(biāo)準(zhǔn)

• 時間上的衡量：使用最糟糕情況下的操作次數(shù)來衡量算法時間上的消耗：它比較的是算法的操作數(shù)，指出了算法運行時間的增速。，按增速由慢到快有：O(log n)，O(n)，O(n * log n)， O(n^2 )，O(n)。算法時間復(fù)雜度描述了，隨著輸入規(guī)模的增大，其運行時間以什么樣的速度增加。通常算法時間分析可以從最好情況，平均情況，最壞情況考量(分別取決于不同的輸入)，而且采用漸進曲線來替代問題規(guī)模n和算法的操作次數(shù)所對應(yīng)的曲線，如：對于輸入規(guī)模為n，操作次數(shù)為n^3 + n^2 + n + log(n)這樣的算法，我們使用O(n^3)作其算法時間復(fù)雜度。
• 空間上的衡量：使用算法在運行時所使用的臨時空間來衡量算法在空間上的消耗。
  以上衡量標(biāo)準(zhǔn)不考慮算法的運行環(huán)境(機器設(shè)備)，只是從算法(解決方案)的角度來分析，具有很強的針對性。

算法復(fù)雜度的分析

• 循環(huán):迭代次數(shù) x 循環(huán)體內(nèi)語句執(zhí)行時間(注意循環(huán)條件和循環(huán)體)

//循環(huán)執(zhí)行n次
for(i = 1;i<=n;i++)
    m = m + 1;//常數(shù)時間c

時間為：c x n = cn =O(n)

• 嵌套循環(huán)：由內(nèi)到外，所有循環(huán)規(guī)模的乘積

//外循環(huán)執(zhí)行n次
for(i = 1;i<=n;i++)
    //內(nèi)循環(huán)執(zhí)行n次
    for(j = 1;i<=n;j++)
        m = m+1;//常數(shù)時間c

時間為：c x n x n = c x n^2 = O(n^2)

• 順序執(zhí)行語句：每條語句的運行時間之和

l = l+1;//常數(shù)時間c1
//循環(huán)執(zhí)行n次
for(i = 1;i<=n;i++)
  t = t+1;//常數(shù)時間c2
//外循環(huán)執(zhí)行n次
for(i = 1;i<=n;i++)
    //內(nèi)循環(huán)執(zhí)行n次
    for(j = 1;i<=n;j++)
        m = m+1;//常數(shù)時間c3

時間為：c1 + n x c2 + n x n x c3 = O(n^2)

• if-else：

//條件：常數(shù)c1
if(array.length() == 0)
    return false;//常數(shù)c2
else{
    //for循環(huán)n次(記array.length()為n)
    for(i = 1;i<=array.length();i++){
        if(array[i].equals(x))//條件執(zhí)行常數(shù)c3
            return false;//常數(shù)c4
    }
}

時間為：c1 + c2 + (c3 + c4) x n = O(n)

• 對數(shù)時間復(fù)雜度:

//第k次循環(huán)時， 2 ^ k = n，即k = log(n)
for(j = 1;i<=n;i = i * 2)
        m = m+1;//常數(shù)時間c1

時間為：O(log(n))

• 遞歸問題解決
  • 分治主定理(未完)
  • 問題規(guī)模減小和遞歸求解主定理(未完)