一例朱、數(shù)據(jù)結(jié)構(gòu)
概念
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。通常情況下乞旦，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來更高的運(yùn)行或者存儲效率续膳。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)。數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)胖替。
數(shù)據(jù)結(jié)構(gòu)組成
- 數(shù)據(jù): 程序的操作對象,用于描述客觀事物研儒。可以輸入到計(jì)算機(jī) 独令，可以被計(jì)算機(jī)處理端朵。
- 數(shù)據(jù)對象: 性質(zhì)相同的數(shù)據(jù)元素的集合(類似于數(shù)組)。
- 數(shù)據(jù)元素: 組成數(shù)據(jù)的對象的基本單位燃箭。
-
數(shù)據(jù)項(xiàng): 一個(gè)數(shù)據(jù)元素由若干數(shù)據(jù)項(xiàng)組成冲呢。
數(shù)據(jù)、數(shù)據(jù)對象招狸、數(shù)據(jù)元素和數(shù)據(jù)項(xiàng)的關(guān)系如下圖：
數(shù)據(jù)結(jié)構(gòu)
邏輯結(jié)構(gòu)
指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)敬拓，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們在計(jì)算機(jī)中的存儲位置無關(guān)裙戏。數(shù)據(jù)的邏輯關(guān)系包括：
- 集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外乘凸，別無其他關(guān)系；（無序的）
- 線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系累榜；
- 樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系营勤；
- 圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系。
物理結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)(也稱為存儲結(jié)構(gòu))壹罚。
數(shù)據(jù)的物理結(jié)構(gòu)的特點(diǎn)是：
-
順序存儲：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系葛作。比如數(shù)組存儲在一串連續(xù)的內(nèi)存中就屬于順序存儲。
-
非順序存儲：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系猖凛。比如非循環(huán)單向鏈表元素存儲的內(nèi)存地址就可以不是連續(xù)的赂蠢，可以根據(jù)元素內(nèi)指向下個(gè)元素的地址找到下個(gè)元素。
常見數(shù)據(jù)結(jié)構(gòu)
二形病、算法
概念
算法是指解題方案的準(zhǔn)確而完整的描述客年，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制漠吻。也就是說量瓜，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出途乃。
數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系
- 數(shù)據(jù)結(jié)構(gòu)和算法兩個(gè)概念間的邏輯關(guān)系貫穿了整個(gè)程序世界绍傲，首先二者表現(xiàn)為不可分割的關(guān)系。沒有數(shù)據(jù)間的有機(jī)關(guān)系和高效處理耍共，程序根本無法設(shè)計(jì)烫饼。
- 數(shù)據(jù)結(jié)構(gòu)為算法提供服務(wù)。算法圍繞數(shù)據(jù)結(jié)構(gòu)操作试读。
-
解決問題和提高程序運(yùn)行速度需要選擇正確的算法杠纵，而高效率和低資源耗費(fèi)的算法的設(shè)計(jì)又依賴于數(shù)據(jù)的結(jié)構(gòu)。例如：算法中經(jīng)常需要對數(shù)據(jù)進(jìn)行增加和刪除用鏈表數(shù)據(jù)結(jié)構(gòu)效率高钩骇，數(shù)組數(shù)據(jù)結(jié)構(gòu)因?yàn)樵黾雍蛣h除需要移動(dòng)數(shù)字每個(gè)元素所以效率低比藻。
數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系就像下圖：
數(shù)據(jù)結(jié)構(gòu)和算法的關(guān)系
算法知識點(diǎn)
- 算法的特性
輸入輸出：算法可以有0個(gè)或者多個(gè)輸入；算法至少要有一個(gè)輸出倘屹，沒有輸出的算法也就沒有意義银亲。
有窮性：算法必須要在執(zhí)行有限個(gè)步驟之后產(chǎn)生出結(jié)果。
確定性：算法的每個(gè)步驟都要有確切的意義纽匙。
可行性：算法的每個(gè)步驟都要切實(shí)有效务蝠，可執(zhí)行。
- 算法的設(shè)計(jì)要求
正確性：算法被要求結(jié)果一定正確烛缔，不正確就沒有意義了馏段。
健壯性：算法內(nèi)的邏輯處理要考慮到對不合理數(shù)據(jù)的處理，即容錯(cuò)能力践瓷。
可讀性：即算法可供其他人閱讀的能力毅弧。
時(shí)間復(fù)雜度：執(zhí)行算法所需要的計(jì)算工作量或時(shí)間長短。一般用O(n)表示当窗，n越大時(shí)間復(fù)雜度越大够坐。一般作為衡量算法效率的主要方法。
空間復(fù)雜度：執(zhí)行算法所需要的輔助（額外使用的）內(nèi)存空間大小崖面。也可用O(n)表示元咙，計(jì)算比時(shí)間復(fù)雜度簡單。
算法的時(shí)間復(fù)雜度
時(shí)間復(fù)雜度計(jì)算規(guī)則
- 用常數(shù)1取代運(yùn)行時(shí)間中所有常數(shù)巫员；eg：3->1 O(1)
- 在修改運(yùn)行次數(shù)函數(shù)中,只保留最高階項(xiàng)庶香；eg: n^ 3+2n^2+5 -> O(n^3)
- 如果在最高階存在且不等于1,則去除這個(gè)項(xiàng)目相乘的常數(shù)；eg：2n^3 -> O(n^3)
時(shí)間復(fù)雜度常見計(jì)算情況
- 常數(shù)階
時(shí)間復(fù)雜度為一個(gè)確定的常數(shù)简识，最終結(jié)果為O(1)赶掖。
//時(shí)間復(fù)雜度 1+1+1+1+1+1 = 6 O(1)
void testSum1(int n) {
int sum = 0; //執(zhí)行1次
sum = (1 + n) * 2; //執(zhí)行1次
sum = (1 + n) * 2; //執(zhí)行1次
sum = (1 + n) * 2; //執(zhí)行1次
sum = (1 + n) * 2; //執(zhí)行1次
sum = (1 + n) * 2; //執(zhí)行1次
}
- 線性階
時(shí)間復(fù)雜度是n的一次冪的表達(dá)式感猛，結(jié)果是O(n)。
//時(shí)間復(fù)雜度 1 + n = n O(n)
void testSum2(int n) {
int x = 0;
for (int i = 0; i < n; i ++) {
x = x + 1; //執(zhí)行n次
}
}
//時(shí)間復(fù)雜度 1 + (n + 1) + n = 2n + 2 O(n)
void testSum3(int n) {
int x = 0; // 1次
for (int i = 0; i <= n; i ++) {
x = x + 1; //執(zhí)行 n + 1 次
}
for (int j = 0; j < n; j ++) {
x = x * 2; //執(zhí)行 n 次
}
}
- 平方階
時(shí)間復(fù)雜度是n^2 的表達(dá)式奢赂，結(jié)果是O(n^2)陪白。
//時(shí)間復(fù)雜度 1 + n + n^2 O(n^2)
void testSum4(int n) {
int x = 0; // 1次
for (int i = 0; i < n; i ++)
{
x = x + 1; //執(zhí)行 n 次
for (int j = 0; j < n; j ++)
{
x = x + 1; //執(zhí)行 n^2 次
}
}
}
//時(shí)間復(fù)雜度 n*(n+1)/2 = n^2/2 + n/2 O(n^2)
void testSum5(int n) {
int x = 0;
for (int i = 0; i < n; i ++) {
for (int j = i; j < n; j ++) {
x = x + 1;
/** 等差數(shù)列求和
i = 0, 執(zhí)行n次
i = 1， 執(zhí)行n-1次
i = 2膳灶， 執(zhí)行n-2次
...
i = n-1, 執(zhí)行 1 次
執(zhí)行總次數(shù)：n*(n+1)/2
*/
}
}
}
- 對數(shù)階
時(shí)間復(fù)雜度是一個(gè)數(shù)的對數(shù)咱士， o(logn)。
//時(shí)間復(fù)雜度 假如x是執(zhí)行次數(shù) 2 ^ x >= n , x = log(2)(n) O(logn)
void testSum6(int n) {
int count = 1;
while (count < n) {
count = count * 2; //執(zhí)行 log(2)(n)次
}
}
- 立方階
時(shí)間復(fù)雜度是包含n^3的表達(dá)式轧钓， O(n^3)序厉。
//時(shí)間復(fù)雜度 n + n*n + n*n*n O(n^3)
void testSum7(int n) {
int x = 1;
for (int i = 0; i < n; i ++) {
x = x + 1; //n次
for (int j = 0; j < n; j ++) {
x = x + 1;//n*n次
for (int k = 0; k < n; k ++) {
x = x + 1;//n*n*n次
}
}
}
}
時(shí)間復(fù)雜度的大小如下：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)
算法的空間復(fù)雜度
一個(gè)算法執(zhí)行的過程中可能用到的空間因素有：
- 寄存本身的指令
- 常數(shù)
- 變量
- 輸入
- 對數(shù)據(jù)進(jìn)行操作的輔助空間
而算法的空間復(fù)雜度的計(jì)算主要是考慮算法執(zhí)行時(shí)所需要的輔助空間。
例子：數(shù)組逆序,將一維數(shù)組a中的n個(gè)數(shù)逆序存放在原數(shù)組中（n<=a.count）毕箍。
方法一：只使用了一個(gè)中間變量temp弛房，空間復(fù)雜度 O(1)
int temp;
for(int i = 0; i < n/2 ; i++){
temp = a[I];
a[i] = a[n-i-1];
a[n-i-1] = temp;
}
方法二：數(shù)組b中創(chuàng)建了n個(gè)元素，空間復(fù)雜度是O(n)
int b[10] = {0};
for(int i = 0; i < n;i++){
b[i] = a[n-i-1];
}
for(int i = 0; i < n; i++){
a[i] = b[i];
}
總結(jié)
- 數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合而柑。
- 算法是是一系列解決問題的清晰指令庭再，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。
- 數(shù)據(jù)結(jié)構(gòu)為算法提供服務(wù)牺堰。算法圍繞數(shù)據(jù)結(jié)構(gòu)操作拄轻。二者密不可分，貫穿整個(gè)程序運(yùn)行伟葫。
- 算法的效率衡量的主要方法是計(jì)算算法的時(shí)間復(fù)雜度恨搓。
