Java數據結構之集合框架與常用算法有哪些

這篇文章主要介紹了Java數據結構之集合框架與常用算法有哪些的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java數據結構之集合框架與常用算法有哪些文章都會有所收獲，下面我們一起來看看吧。

1 集合框架

1.1 集合框架概念

Java 集合框架 Java Collection Framework ，又被稱為容器 container ，是定義在 java.util 包下的一組接口 interfaces和其實現類 classes 。

其主要表現為將多個元素 element 置于一個單元中，用于對這些元素進行快速、便捷的存儲 store 、檢索 retrieve 、管理 manipulate ，即平時我們俗稱的增刪查改 CRUD 。

類和接口總覽：

1.2 容器涉及的數據結構

Collection：是一個接口，包含了大部分容器常用的一些方法

List：是一個接口，規范了ArrayList 和 LinkedList中要實現的方法

• ArrayList：實現了List接口，底層為動態類型順序表

• LinkedList：實現了List接口，底層為雙向鏈表

Stack：底層是棧，棧是一種特殊的順序表

Queue：底層是隊列，隊列是一種特殊的順序表

Deque：是一個接口

Set：集合，是一個接口，里面放置的是K模型

• HashSet：底層為哈希桶，查詢的時間復雜度為O(1)

• TreeSet：底層為紅黑樹，查詢的時間復雜度為O( ),關于key有序的

Map：映射，里面存儲的是K-V模型的鍵值對

• HashMap：底層為哈希桶，查詢時間復雜度為O(1)

• TreeMap：底層為紅黑樹，查詢的時間復雜度為O( )，關于key有序

2 算法

2.1 算法概念

算法(Algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數據轉化成輸出結果。

2.2 算法效率

算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度。 時間復雜度主要衡量的是一個算法的運行速度，而空間復雜度主要衡量一個算法所需要的額外空間，在計算機發展的早期，計算機的存儲容量很小。所以對空間復雜度很是在乎。但是經過計算機行業的迅速發展，計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間復雜度。

3 時間復雜度

3.1 時間復雜度概念

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

3.2 大O的漸進表示法

// 請計算一下func1基本操作執行了多少次？
void func1(int N){
	int count = 0;
	for (int i = 0; i < N ; i++) {
		for (int j = 0; j < N ; j++) {
			count++;
		}
	}
	for (int k = 0; k < 2 * N ; k++) {
		count++;
	} 
	int M = 10;
	while ((M--) > 0) {
		count++;
	} 
	System.out.println(count);
}

Func1 執行的基本操作次數 ：F(N)=N^2+2*N+10

• N = 10 F(N) = 130

• N = 100 F(N) = 10210

• N = 1000 F(N) = 1002010

實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法。

大O符號（Big O notation）：是用于描述函數漸進行為的數學符號

3.3 推導大O階方法

• 用常數1取代運行時間中的所有加法常數。

• 在修改后的運行次數函數中，只保留最高階項。

• 如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階。

使用大O的漸進表示法以后，Func1的時間復雜度為：O(n^2)

• N = 10 F(N) = 100

• N = 100 F(N) = 10000

• N = 1000 F(N) = 1000000

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數。另外有些算法的時間復雜度存在最好、平均和最壞情況：

最壞情況：任意輸入規模的最大運行次數(上界)

平均情況：任意輸入規模的期望運行次數

最好情況：任意輸入規模的最小運行次數(下界)

例如：在一個長度為N數組中搜索一個數據x

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到

在實際中一般情況關注的是算法的最壞運行情況，所以數組中搜索數據時間復雜度為O(N)

4 空間復雜度

空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 。空間復雜度不是程序占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法。

實例1:

// 計算bubbleSort的空間復雜度？
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;
		}
	}
}

實例2:

// 計算fibonacci的空間復雜度？
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;
}

實例3:

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

• 實例1使用了常數個額外空間，所以空間復雜度為 O(1)

• 實例2動態開辟了N個空間，空間復雜度為 O(N)

• 實例3遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間復雜度為O(N)

關于“Java數據結構之集合框架與常用算法有哪些”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Java數據結構之集合框架與常用算法有哪些”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。