柚子快報激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)前置知識

http://yzkb.51969.com/

這里寫目錄標題

基本概念與術(shù)語數(shù)據(jù)數(shù)據(jù)元素數(shù)據(jù)項數(shù)據(jù)對象數(shù)據(jù)結(jié)構(gòu)

邏輯結(jié)構(gòu)和物理結(jié)構(gòu)物理結(jié)構(gòu)順序存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu)

邏輯結(jié)構(gòu)集合結(jié)構(gòu)線性結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)

算法時間復(fù)雜度和空間復(fù)雜度大O的漸進表示法時間復(fù)雜度常數(shù)階線性階對數(shù)階平方階常見時間復(fù)雜度

空間復(fù)雜度

最好情況與平均情況于最壞情況

基本概念與術(shù)語

概念皆來自于《大話數(shù)據(jù)結(jié)構(gòu)》。

數(shù)據(jù)

數(shù)據(jù)的概念：是描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別并輸入給計算機處理的符號集合。 其實就是可以輸入到計算機中，可以被計算機處理的字符。像文件，圖像，聲音，數(shù)字等等都是可以通過編碼轉(zhuǎn)換為字符來處理。

數(shù)據(jù)元素

數(shù)據(jù)元素的概念：是組成數(shù)據(jù)的，有一定意義的基本單位，在計算機中通常作為整體處理，也稱為記錄。

就像數(shù)學中由多個集合（子集合）構(gòu)成的集合。子集就像數(shù)據(jù)元素一樣

數(shù)據(jù)項

數(shù)據(jù)項概念：一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。 數(shù)據(jù)項就像集合中的元素。

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

數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

關(guān)系： 用∈代替一下‘包含于’關(guān)系 數(shù)據(jù)項∈數(shù)據(jù)元素∈數(shù)據(jù)對象∈數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)概念:是互相之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

這是根據(jù)視點來區(qū)分的數(shù)據(jù)結(jié)構(gòu)。

物理結(jié)構(gòu)

物理結(jié)構(gòu)：是指數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲形式。

順序存儲結(jié)構(gòu)

是把數(shù)據(jù)元素存放在地址連續(xù)的存儲單元里，其數(shù)據(jù)間的邏輯結(jié)構(gòu)關(guān)系和物理結(jié)構(gòu)關(guān)系是一致的。

鏈式存儲結(jié)構(gòu)

是把數(shù)據(jù)元素存放在任意位置的存儲單元里，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。

邏輯結(jié)構(gòu)

是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關(guān)系。

集合結(jié)構(gòu)

集合結(jié)構(gòu)中的數(shù)據(jù)元素除了同屬于一個集合外，他們之間沒有其他關(guān)系。

線性結(jié)構(gòu)

線性結(jié)構(gòu)中的數(shù)據(jù)元素之間是一對一的關(guān)系。

樹形結(jié)構(gòu)

樹形結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一種一對多的層次關(guān)系。

圖形結(jié)構(gòu)

圖形結(jié)構(gòu)中的數(shù)據(jù)元素是多對多的關(guān)系。

算法

算法的定義：算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列。并且每條指令表示一個或多個操作。 算法五大特性：輸入，輸出，有窮性，確定性，可行性。

當多個算法都可以解決問題（在保證了正確性、可讀性、健壯性），我們一般要考慮算法的時間效率，空間效率。我們就要用時間復(fù)雜度和空間復(fù)雜度來衡量。

時間復(fù)雜度和空間復(fù)雜度

其實我們要求時間復(fù)雜度就把語句執(zhí)行次數(shù)給加起來表示為一個函數(shù)，空間復(fù)雜度開辟空間次數(shù)加起來表示為一個函數(shù)。然后將函數(shù)由大O的漸進表示法來表示。求得的就是復(fù)雜度。

我們通常使用大O的漸進表示法來表示時間復(fù)雜度和空間復(fù)雜度。

大O的漸進表示法

規(guī)則： 1.用常數(shù)1來取代運行時間中的所有加法常數(shù)； 2.在修改后的運行次數(shù)函數(shù)中，只保留最高階項； 3.如果最高階項存在且系數(shù)不為1，則將系數(shù)修改為1。

時間復(fù)雜度

常數(shù)階

int n = 100;

int sum = (n+1)*n/2;

這個高斯公式求和就是函數(shù)為3，常數(shù)都表示為1，大O漸進法（時間復(fù)雜度）表示就是O(1)。

線性階

int n = 100;

int sum = 0;

for(int i = 0; i < n; i++){

sum += i;

}

這個求和就是函數(shù)為n+2，保留最高階，大O漸進法（時間復(fù)雜度）表示就是O(n)。

對數(shù)階

int count = 1;

while(count < n){

count *= 2;

}

這個就是函數(shù)為logN+1，保留最高階，大O漸進法（時間復(fù)雜度）表示就是O(logN)。

平方階

for(int i = 0; i < n; i++){

for(int j = 0; j < n; j++){

System.out.print("0 ");

}

}

這個的函數(shù)為nn + 1，保留最高階，大O漸進法（時間復(fù)雜度）表示就是O(nn)。

常見時間復(fù)雜度

O(1) < O(logN) < O(N) < O(NlogN) < O(NN) < O(2^N) < O(N!) < O(N*N)

空間復(fù)雜度

空間復(fù)雜度和時間復(fù)雜度求法完全一樣，只不過是將執(zhí)行次數(shù)變?yōu)殚_辟空間次數(shù)。

int factorial(int N) {

return N < 2 ? N : factorial(N-1)*N;

}

如上面代碼每一次調(diào)用都要開辟一次，遞歸了N次?？臻g復(fù)雜度就是O(N)。

最好情況與平均情況于最壞情況

最好情況就是當前要解決的問題完全契合當前算法。像寫一個冒泡排序，給的數(shù)組本身就是有序的，此時直接返回值時間復(fù)雜度就是O(1)。

平均情況就是所有情況中最有意義的，因為它是期望的運行時間。

最壞情況，一般不說明我們像上面將訴的方法求的復(fù)雜度一般是最壞情況。

柚子快報激活碼778899分享：【數(shù)據(jù)結(jié)構(gòu)】數(shù)據(jù)結(jié)構(gòu)前置知識

http://yzkb.51969.com/

相關(guān)鏈接