大話(huà)數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)：是描述客觀事物的符號(hào)，是計(jì)算機(jī)中可以操作的對(duì)象法梯，是能被計(jì)算機(jī)識(shí)別苔货，并輸入給計(jì)算機(jī)處理的符號(hào)集合。數(shù)據(jù)不僅僅包括整型鹊汛、實(shí)型等數(shù)值類(lèi)型蒲赂，還包括字符及聲音阱冶、圖像刁憋、視頻等非數(shù)值類(lèi)型。
數(shù)據(jù)元素: 是組成數(shù)據(jù)的, 有一定意義的基本單位, 在計(jì)算機(jī)中通常作為整體處理, 也被稱(chēng)為記錄
數(shù)據(jù)項(xiàng): 一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成
數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合木蹬，是數(shù)據(jù)的子集至耻。
邏輯結(jié)構(gòu)與物理結(jié)構(gòu):
邏輯結(jié)構(gòu):
1. 集合結(jié)構(gòu): 集合結(jié)構(gòu)中的數(shù)據(jù)元素除了屬于一個(gè)集合外, 他們之間沒(méi)有其他關(guān)系
2. 線(xiàn)性結(jié)構(gòu): 線(xiàn)性結(jié)構(gòu)中的數(shù)據(jù)元素是一對(duì)一的關(guān)系
3. 樹(shù)形結(jié)構(gòu): 數(shù)據(jù)元素之間存在一種一對(duì)多的層次關(guān)系
4. 圖形結(jié)構(gòu): 數(shù)據(jù)元素是多對(duì)多的關(guān)系
物理結(jié)構(gòu): 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)形式
數(shù)據(jù)類(lèi)型: 指一組性質(zhì)相同的值得集合及定義在此集合上的一些操作的總稱(chēng)
如:
int,string,float
1. 原子類(lèi)型: 是不可以再分解的基本類(lèi)型, 包括整型, 實(shí)型, 字符型
2. 結(jié)構(gòu)類(lèi)型: 由若干個(gè)類(lèi)型組合而成, 是可以分解的
抽象: 抽取事物具有的普遍性的本質(zhì). 它是抽出問(wèn)題的特征而忽略非本質(zhì)的細(xì)節(jié), 是對(duì)具體事物的一個(gè)概括. 抽象是一種思考問(wèn)題的方式, 他隱藏了繁雜的細(xì)節(jié), 只保留實(shí)現(xiàn)目標(biāo)所必須的信息
抽象數(shù)據(jù)類(lèi)型: (Abstract Data Type, ADT) 是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作. 抽象數(shù)據(jù)類(lèi)型的定義取決于一組邏輯特性, 而與其在計(jì)算機(jī)內(nèi)部如何表現(xiàn)和實(shí)現(xiàn)無(wú)關(guān)
數(shù)據(jù)結(jié)構(gòu)定義: 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合.
算法: 算法是解決特定問(wèn)題求解步驟的描述, 在計(jì)算機(jī)中表現(xiàn)為指令的有限序列, 并且每條指令表示一個(gè)或者多個(gè)操作
算法: Algorithm
算法的特性:
- 輸入輸出
- 有窮性
- 確定性
- 可執(zhí)行性
算法設(shè)計(jì)的要求:
- 正確性
- 1. 沒(méi)有語(yǔ)法錯(cuò)誤
- 2. 合法的輸入產(chǎn)生正確的結(jié)果
- 3. 對(duì)非法輸入,得到滿(mǎn)足規(guī)格說(shuō)明的結(jié)果(輸出對(duì)應(yīng)的錯(cuò)誤)
- 4. 哪怕再刁難的測(cè)試數(shù)據(jù)都能返回正確的結(jié)果
- 可讀性
- 健壯性
- 時(shí)間效率高 和 存儲(chǔ)量低
2.7 算法效率的度量方法
- 2.7.1 事后統(tǒng)計(jì)方法 (不采納)
- 2.7.2 事前分析估算方法
- 1. 算法采用的策略, 方法
- 2. 編譯產(chǎn)生的代碼質(zhì)量
- 3. 問(wèn)題的輸入規(guī)模
- 4. 機(jī)器執(zhí)行指令的速度
第一種算法
```
int i , sum = 0 , n = 100; /* 執(zhí)行1次 */
for (i = 1, i<= n, i++) /* 執(zhí)行了 n+1 */
{
sum = sum + i; /* 執(zhí)行 n 次 */
}
printf("%d" , sum); /* 執(zhí)行 1 次 */
阿道夫
愛(ài)的方式
第二種算法
```
int sum = 0, n = 100; /* 執(zhí)行一次 */
sum = (1 + n) * n / 2; /* 執(zhí)行一次 */
printf("%d" , sum); /* 執(zhí)行一次 */
```
2.8 函數(shù)的漸近增長(zhǎng)
函數(shù)的漸近: 輸入規(guī)模n在沒(méi)有限制的情況下，只要超過(guò)一個(gè)數(shù)值N镊叁，這個(gè)函數(shù)就總是大于另一個(gè)函數(shù)
給定兩個(gè)函數(shù)f(n)和g(n)尘颓，如果存在一個(gè)整數(shù)N，使得對(duì)于所有的n>N晦譬，f(n)總是比g(n)大疤苹，那么，我們說(shuō)f(n)的增長(zhǎng)漸近快于g(n)
判斷一個(gè)算法的效率時(shí)敛腌，函數(shù)中的常數(shù)和其他次要項(xiàng)常澄酝粒可以忽略，而更應(yīng)該關(guān)注主項(xiàng)（最高階項(xiàng)）的階數(shù)
2.9 算法時(shí)間復(fù)雜度
2.9.1 算法時(shí)間復(fù)雜度定義
在進(jìn)行算法分析時(shí)像樊，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)尤莺，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度生棍，也就是算法的時(shí)間量度颤霎，記作：T(n)=O(f(n))。它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同友酱，稱(chēng)作算法的漸近時(shí)間復(fù)雜度晴音，簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)缔杉。
O(1)叫常數(shù)階段多、
O(n)叫線(xiàn)性階、
O(n2)叫平方階
2.9.2 推導(dǎo)大O階方法
1．用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)壮吩。
2．在修改后的運(yùn)行次數(shù)函數(shù)中进苍，只保留最高階項(xiàng)。
3．如果最高階項(xiàng)存在且不是1鸭叙，則去除與這個(gè)項(xiàng)相乘的常數(shù)觉啊。
2.10 常見(jiàn)的時(shí)間復(fù)雜度
執(zhí)行次數(shù) 函數(shù)階 非正式術(shù)語(yǔ)
12 O(1) 常數(shù)階
2n+3 O(n) 線(xiàn)性階
3n^2+2n+1 O(n^2) 平方階
5log2n+20 O(logn) 對(duì)數(shù)階
2n+3nlog2n+19 O(nlogn) nlogn階
6n^3+2n^2+3n+4 O(n3) 立方階
2n O(2n) 指數(shù)階
常用的時(shí)間復(fù)雜度所耗費(fèi)的時(shí)間從小到大依次是：
O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)
2.11 最壞情況和平均情況
最壞情況運(yùn)行時(shí)間是一種保證, 那就是運(yùn)行時(shí)間將不會(huì)再壞了. 再應(yīng)用中, 這是一種最重要的需求, 通常, 除非特別指定, 我們提到的運(yùn)行時(shí)間都是最壞情況的運(yùn)行時(shí)間
平均運(yùn)行時(shí)間是所有情況中最有意義的, 因?yàn)樗瞧谕倪\(yùn)行時(shí)間.
2.12 算法空間復(fù)雜度
算法的空間復(fù)雜度通過(guò)計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn), 算法空間復(fù)雜度的計(jì)算公式記作: S(n) = O(f(n)) , 其中, n 為問(wèn)題的規(guī)模, f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)
