一、數(shù)據(jù)類(lèi)型

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

站在計(jì)算機(jī)和程序員的角度：計(jì)算機(jī)只認(rèn)識(shí) 0 和 1 照宝，如果直接讓程序員操作0和1，想必會(huì)瘋掉一批人句葵，所以厕鹃，由編譯器 和編程語(yǔ)言將他們抽象成基本數(shù)據(jù)類(lèi)型供廣大猿類(lèi)使用。所以乍丈，通過(guò)編譯器和編程語(yǔ)言來(lái)確定他們?cè)谟?jì)算機(jī)中的長(zhǎng)度和可以進(jìn)行的操作剂碴。

舉例：例如Java中基本類(lèi)型int占用2字節(jié)(16位)，而在變他們可以進(jìn)行 " +诗赌，-汗茄，x，/“ 等操作铭若，不可以進(jìn)行并，交递览，差等操作叼屠。所以它的值集：-2^15 ~ 2^15-1(因?yàn)?的存在所以需要-1)，操作集合：” +绞铃，-镜雨，x，/ “ 等

分類(lèi)：

• 基本數(shù)據(jù)類(lèi)型
  系統(tǒng)定義的(編程語(yǔ)言提供的)數(shù)據(jù)類(lèi)型成為基本數(shù)據(jù)類(lèi)型儿捧，如Java中的int,float,double,char等荚坞。
• 用戶(hù)自定義數(shù)據(jù)類(lèi)型
  用戶(hù)可以自己定義的數(shù)據(jù)類(lèi)型，如Java中的類(lèi)菲盾。

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

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

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

• 數(shù)據(jù)的邏輯結(jié)構(gòu) ：反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu),主要是指他們之間的前后關(guān)系诡挂，如集合關(guān)系(前后無(wú)關(guān)系碎浇，但同屬一集合)，線(xiàn)性結(jié)構(gòu)(前后一對(duì)一)璃俗，樹(shù)形結(jié)構(gòu)(前后一對(duì)多)奴璃，圖形結(jié)構(gòu)(前后多對(duì)多)。
• 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式城豁，也就是數(shù)據(jù)在計(jì)算機(jī)內(nèi)的表示苟穆。如順序存儲(chǔ)，鏈接存儲(chǔ)唱星，散列存儲(chǔ)鞭缭，索引存儲(chǔ)等。一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲(chǔ)結(jié)構(gòu)魏颓。
• 數(shù)據(jù)的運(yùn)算結(jié)構(gòu)：也就是這些數(shù)據(jù)可以進(jìn)行哪些運(yùn)算操作岭辣。

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

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

數(shù)據(jù)類(lèi)型：計(jì)算機(jī)程序中的數(shù)據(jù)對(duì)象以及定義在這個(gè)數(shù)據(jù)對(duì)象集合上的一組操作的總稱(chēng)氏豌。
從名字上看，它表示的是數(shù)據(jù)的類(lèi)型热凹，也就是將數(shù)據(jù)按照數(shù)據(jù)結(jié)構(gòu)進(jìn)行分類(lèi)后泵喘，所屬的類(lèi)型。即同一類(lèi)數(shù)據(jù)的所有稱(chēng)為一個(gè)數(shù)據(jù)類(lèi)型般妙。它最早出現(xiàn)在高級(jí)程序語(yǔ)言中纪铺，用戶(hù)來(lái)刻畫(huà)操作對(duì)象的特征，按照“值”的不同碟渺，可以分為非結(jié)構(gòu)的原子數(shù)據(jù)類(lèi)型和結(jié)構(gòu)類(lèi)型鲜锚。
所以,一類(lèi)數(shù)據(jù)結(jié)構(gòu)對(duì)應(yīng)著一種數(shù)據(jù)類(lèi)型。

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

四速妖、算法

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

特征：

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

衡量標(biāo)準(zhǔn)：評(píng)價(jià)一個(gè)算法的好壞的標(biāo)準(zhǔn)

• 時(shí)間上的衡量：使用最糟糕情況下的操作次數(shù)來(lái)衡量算法時(shí)間上的消耗：它比較的是算法的操作數(shù)旅择，指出了算法運(yùn)行時(shí)間的增速。侣姆，按增速由慢到快有：O(log n)生真，O(n)，O(n * log n)捺宗， O(n^2 )柱蟀，O(n)。算法時(shí)間復(fù)雜度描述了蚜厉，隨著輸入規(guī)模的增大长已，其運(yùn)行時(shí)間以什么樣的速度增加。通常算法時(shí)間分析可以從最好情況昼牛，平均情況术瓮，最壞情況考量(分別取決于不同的輸入)，而且采用漸進(jìn)曲線(xiàn)來(lái)替代問(wèn)題規(guī)模n和算法的操作次數(shù)所對(duì)應(yīng)的曲線(xiàn)匾嘱，如：對(duì)于輸入規(guī)模為n轴术，操作次數(shù)為n^3 + n^2 + n + log(n)這樣的算法胃惜，我們使用O(n^3)作其算法時(shí)間復(fù)雜度刀诬。
• 空間上的衡量：使用算法在運(yùn)行時(shí)所使用的臨時(shí)空間來(lái)衡量算法在空間上的消耗汹忠。
  以上衡量標(biāo)準(zhǔn)不考慮算法的運(yùn)行環(huán)境(機(jī)器設(shè)備)诉植，只是從算法(解決方案)的角度來(lái)分析澈蝙，具有很強(qiáng)的針對(duì)性拔鹰。

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

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

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

時(shí)間為：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ù)時(shí)間c

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

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

l = l+1;//常數(shù)時(shí)間c1
//循環(huán)執(zhí)行n次
for(i = 1;i<=n;i++)
  t = t+1;//常數(shù)時(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ù)時(shí)間c3

時(shí)間為：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
    }
}

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

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

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

時(shí)間為：O(log(n))

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