數(shù)據(jù)結(jié)構(gòu)和算法入門(mén)（時(shí)間/空間復(fù)雜度介紹–java版）

write in front

作者：@ 向大佬學(xué)習(xí)
專(zhuān)欄：@ 數(shù)據(jù)結(jié)構(gòu)（java版）
作者簡(jiǎn)介：大二學(xué)生 希望能學(xué)習(xí)其同學(xué)和大佬的經(jīng)驗(yàn)！

本篇博客簡(jiǎn)介：主要介紹數(shù)據(jù)結(jié)構(gòu)的一些概念知識(shí)為以后學(xué)習(xí)打下基礎(chǔ)！

今日名言：希望在我們心中，未來(lái)是靠雙手去創(chuàng)造。

本章目標(biāo)
一、簡(jiǎn)單認(rèn)識(shí)集合框架
二、背后所涉及的數(shù)據(jù)結(jié)構(gòu)合算法
三、時(shí)間復(fù)雜度
四、空間復(fù)雜度

一、簡(jiǎn)單認(rèn)識(shí)集合框架

Java 集合框架 Java Collection Framework，又被稱(chēng)為容器 container ，是定義在 java.util 包下的一組接口 interfaces和其實(shí)現(xiàn)類(lèi) classes 。

其主要表現(xiàn)為將多個(gè)元素 element 置于一個(gè)單元中，用于對(duì)這些元素進(jìn)行快速、便捷的存儲(chǔ) store 、檢索 retrieve 、管理manipulate ，即平時(shí)我們俗稱(chēng)的增刪查改 CRUD.

例如，一副撲克牌(一組牌的集合)、一個(gè)郵箱(一組郵件的集合)、一個(gè)通訊錄(一組姓名和電話(huà)的映射關(guān)系)等等。

下面的圖給出了java中常用集合的繼承體系圖：

java的集合實(shí)際上就是各種基本的數(shù)據(jù)結(jié)構(gòu)（棧、隊(duì)列，hash表等）基于業(yè)務(wù)需求進(jìn)而演變出的java特有的數(shù)據(jù)結(jié)構(gòu)。

二、背后所涉及的數(shù)據(jù)結(jié)構(gòu)合算法

1.什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(Data Structure)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式，指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

用通俗的話(huà)來(lái)解釋數(shù)據(jù)結(jié)構(gòu)可以理解為：數(shù)據(jù)+結(jié)構(gòu)。數(shù)據(jù)是描述客觀事物的符號(hào)，為程序操控，存儲(chǔ)再計(jì)算機(jī)上，結(jié)構(gòu)包括數(shù)據(jù)的邏輯和存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）。

在具體學(xué)習(xí)容器之前我們先簡(jiǎn)單了解一下它所對(duì)應(yīng)的特定數(shù)據(jù)結(jié)構(gòu)的封裝。

1. Collection：是一個(gè)接口，包含了大部分容器常用的一些方法
2. List：是一個(gè)接口，規(guī)范了ArrayList 和 LinkedList中要實(shí)現(xiàn)的方法
   ArrayList：實(shí)現(xiàn)了List接口，底層為動(dòng)態(tài)類(lèi)型順序表
   LinkedList：實(shí)現(xiàn)了List接口，底層為雙向鏈表
3. Stack：底層是棧，棧是一種特殊的順序表
4. Queue：底層是隊(duì)列，隊(duì)列是一種特殊的順序表
5. Deque：是一個(gè)接口
6. Set：集合，是一個(gè)接口，里面放置的是K模型
   HashSet：底層為哈希桶，查詢(xún)的時(shí)間復(fù)雜度為O(1)
   TreeSet：底層為紅黑樹(shù)，查詢(xún)的時(shí)間復(fù)雜度為O(logN ),關(guān)于key有序的
7. Map：映射，里面存儲(chǔ)的是K-V模型的鍵值對(duì)
   HashMap：底層為哈希桶，查詢(xún)時(shí)間復(fù)雜度為O(1)
   TreeMap：底層為紅黑樹(shù)，查詢(xún)的時(shí)間復(fù)雜度為O(logN )，關(guān)于key有序

2.什么是算法

算法(Algorithm):就是定義良好的計(jì)算過(guò)程，他取一個(gè)或一組的值為輸入，并產(chǎn)生出一個(gè)或一組值作為輸出。簡(jiǎn)單來(lái)說(shuō)算法就是一系列的計(jì)算步驟，用來(lái)將輸入數(shù)據(jù)轉(zhuǎn)化成輸出結(jié)果。

3.算法效率

算法效率分析分為兩種：第一種是時(shí)間效率，第二種是空間效率。時(shí)間效率被稱(chēng)為時(shí)間復(fù)雜度，而空間效率被稱(chēng)作空間復(fù)雜度。 時(shí)間復(fù)雜度主要衡量的是一個(gè)算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個(gè)算法所需要的額外空間。

在計(jì)算機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲(chǔ)容量很小。所以對(duì)空間復(fù)雜度很是在乎。但是經(jīng)過(guò)計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲(chǔ)容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。

三、時(shí)間復(fù)雜度

1.時(shí)間復(fù)雜度的概念

時(shí)間復(fù)雜度的定義：在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)數(shù)學(xué)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上說(shuō)，是不能算出來(lái)的，只有你把你的程序放在機(jī)器上跑起來(lái)，才能知道。但是我們需要每個(gè)算法都上機(jī)測(cè)試嗎？是可以都上機(jī)測(cè)試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。

2.大O的漸進(jìn)表示法

實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法。
大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

3.推導(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ù)。得到的結(jié)果就是大O階。

另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況,在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況。

4.常見(jiàn)時(shí)間復(fù)雜度計(jì)算舉例

[實(shí)例1]

//計(jì)算func2的時(shí)間復(fù)雜度？
void func2(int N) {int count = 0;for (int k = 0; k < 2 * N ; k++) {count++;}int M = 10;while ((M--) > 0) {count++;}System.out.println(count);
}

根據(jù)循環(huán)可得，基本操作執(zhí)行了2*N+10次，通過(guò)推導(dǎo)大O階的方法得到時(shí)間復(fù)雜度是O（N）。

[實(shí)例2]

//計(jì)算func3的時(shí)間復(fù)雜度？
void func3(int N, int M) {int count = 0;for (int k = 0; k < M; k++) {count++;}for (int k = 0; k < N ; k++) {count++;}System.out.println(count);
}

根據(jù)循環(huán)可得，基本操作執(zhí)行了M+N次，由于M和N都是未知的，通過(guò)推導(dǎo)大O階的方法得到時(shí)間復(fù)雜度是O（M+N）。

[實(shí)例3]

//計(jì)算func4的時(shí)間復(fù)雜度？
void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {count++;}System.out.println(count);
}

根據(jù)循環(huán)可得，基本操作執(zhí)行了100次，通過(guò)推導(dǎo)大O階的方法得到時(shí)間復(fù)雜度是O（1）。

[實(shí)例4]

//計(jì)算bubbleSort的時(shí)間復(fù)雜度？
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}

(1)最好情況：排序的數(shù)組本來(lái)就是有序的，那么外層循環(huán)只會(huì)執(zhí)行一次，而內(nèi)層循環(huán)會(huì)執(zhí)行N次，所以得到的時(shí)間復(fù)雜度是O（N）。
(2)最壞情況，數(shù)組是完全無(wú)序的，那么外層循環(huán)合內(nèi)層循環(huán)都會(huì)執(zhí)行N次，內(nèi)層循環(huán)執(zhí)行次數(shù)從N開(kāi)始，每次減少1，構(gòu)成一個(gè)等差數(shù)列。

因?yàn)閺?fù)雜度的計(jì)算都是看最壞情況：執(zhí)行了1/2*N²+1/2次，通過(guò)推導(dǎo)大O階的方法得到時(shí)間復(fù)雜度是O（N²）。

[實(shí)例5]

//計(jì)算binarySearch的時(shí)間復(fù)雜度？
int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2);if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;
}

先講結(jié)論：
最好情況：基本操作執(zhí)行1次(要找的那個(gè)數(shù)恰好在中間，第一次就找到)
最壞情況：基本操作執(zhí)行l(wèi)og₂N次（以2為底）
下面的圖是解釋

2^x=N, x=log₂N,所以時(shí)間復(fù)雜度是O（logN）。

[實(shí)例6]

//計(jì)算階乘遞歸factorial的時(shí)間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}

基本操作執(zhí)行了N次，所以時(shí)間復(fù)雜度是O（N）。

[實(shí)例7]

//計(jì)算斐波那契遞歸fibonacci的時(shí)間復(fù)雜度？
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

計(jì)算時(shí)間復(fù)雜度并不一定要精準(zhǔn)計(jì)算基本操作數(shù)，當(dāng)N足夠大時(shí)，左邊缺少的一部分就可以忽略不計(jì)，
所以根據(jù)等比數(shù)列求和公式可得：2^N-1,通過(guò)推導(dǎo)大O階的方法得到時(shí)間復(fù)雜度是O（2^N）。

四、空間復(fù)雜度

1.空間復(fù)雜度概念

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度 ?？臻g復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒(méi)太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)?？臻g復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類(lèi)似，也使用大O漸進(jìn)表示法。

2.常見(jiàn)空間復(fù)雜度的計(jì)算

[實(shí)例1]

//計(jì)算bubbleSort的空間復(fù)雜度？
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}
}

使用了常數(shù)個(gè)額外空間，所以空間復(fù)雜度是O（1）。

[實(shí)例2]

//計(jì)算fibonacci的空間復(fù)雜度？
int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;
}

動(dòng)態(tài)開(kāi)辟了N個(gè)空間，空間復(fù)雜度為O(N)。

[實(shí)例3]

//計(jì)算階乘遞歸Factorial的空間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}

遞歸調(diào)用了N次，每次調(diào)用參數(shù)都會(huì)壓棧開(kāi)辟臨時(shí)空間，開(kāi)辟了N個(gè)棧幀，每個(gè)棧幀使用常數(shù)個(gè)空間（壓棧），所以空間復(fù)雜度是O(N)。

[實(shí)例4]

//計(jì)算階乘遞歸Factorial的空間復(fù)雜度？
long fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

通過(guò)觀察上面的圖進(jìn)行分析，每次遞歸都會(huì)開(kāi)辟對(duì)應(yīng)的棧幀并將參數(shù)壓棧，這里需要注意的是每次每次遞歸調(diào)用結(jié)束后，相應(yīng)的棧幀空間會(huì)被銷(xiāo)毀釋放，不計(jì)入空間復(fù)雜度中。
當(dāng)一次遞歸又分為兩次遞歸調(diào)用時(shí)，只有左邊的調(diào)用返回后才執(zhí)行右邊的調(diào)用。
所以圖中的每一層其實(shí)最終只有一個(gè)棧幀空間，所以求第N個(gè)斐波那契數(shù)列的遞歸深度為N,也就是開(kāi)辟了N個(gè)棧幀
每次遞歸的棧幀空間大小都是一樣的，所以每次遞歸中所需的空間是個(gè)常量，并不會(huì)隨著N的變化而變化，每次遞歸的空間復(fù)雜度就是O（1）.
開(kāi)辟N個(gè)棧幀，每個(gè)棧幀使用了常數(shù)個(gè)空間累加，所以最終的空間復(fù)雜度為O(N).