Java數(shù)據(jù)結(jié)構(gòu)之復(fù)雜度篇
一.算法效率
算法效率分析分為兩種：時間效率、空間效率。其中時間效率被稱為時間復(fù)雜度，空間效率被稱為空間復(fù)雜度。
時間復(fù)雜度主要衡量的是一個算法的運行速度，而空間復(fù)雜度主要衡量一個算法所需要的額 外空間
由于早期計算機儲存容量很少，所以通常是浪費時間來換取空間。而隨著計算機的高速發(fā)展，計算機的存儲容量已經(jīng)達到了很高水平，所以現(xiàn)在通常是浪費空間換取時間
二. 時間復(fù)雜度
1.時間復(fù)雜度的概念
在計算機科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間。但是一個算法執(zhí)行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程序放在機器上跑起來，才能知道。全部算法的上機測試顯然是不現(xiàn)實的。于是才有了時間復(fù)雜度的分析方式：算法中的基本操作的執(zhí)行次數(shù)，是為算法的時間復(fù)雜度。
有些算法的時間復(fù)雜度存在最壞、最好和平均情況。一般來說，實際情況中，我們所求的時間復(fù)雜度指的是最壞情況
最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界) 平均情況：任意輸入規(guī)模的期望運行次數(shù) 最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)
2.大O的漸進表示方法
實際中我們計算時間復(fù)雜度時，我們其實并不一定要計算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用的就是大O的漸進表示法
接下來我們看看推導(dǎo)大O階的基本原則
1、用常數(shù)1取代運行時間中的所有加法常數(shù)。
2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。
3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階
3.實例分析與計算
//計算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;
}
}
}該算法最壞情況下執(zhí)行了(N*(N-1))/2次，通過推導(dǎo)大O階方法可以得出其時間復(fù)雜度為O(N)
// 計算binarySearch的時間復(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;
else
return mid;
}
return -1;
}該算法最壞情況下執(zhí)行O(logN)次，時間復(fù)雜度為 O(logN)。ps：logN在算法分析中表示是底數(shù)為2，對數(shù)為N。有些地方會寫成lgN。該算法為二分查找，可以通過畫圖來借助理解，得出表達式為：N/2^X=1，X就是執(zhí)行操作的次數(shù)
// 計算階乘遞歸factorial的時間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}基本操作遞歸了N次，時間復(fù)雜度為O(N)
// 計算斐波那契遞歸fibonacci的時間復(fù)雜度
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}基本操作遞歸了2^N次，時間復(fù)雜度為O(2^N)
三.空間復(fù)雜度
1.空間復(fù)雜度的概念
空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 ?？臻g復(fù)雜度不是程序占用了多少bytes的空間，而是算的是變量的個數(shù)?？臻g復(fù)雜度計算規(guī)則基本跟時間復(fù)雜度類似，也使用大O漸進表示法
2.實例分析與計算
// 計算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ù)個額外空間，所以空間復(fù)雜度為 O(1)
// 計算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;
}該算法動態(tài)開辟了N個空間，空間復(fù)雜度為 O(N)
// 計算階乘遞歸Factorial的時間復(fù)雜度
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}該算法遞歸調(diào)用了N次，開辟了N個棧幀，每個棧幀使用了常數(shù)個空間?？臻g復(fù)雜度為O(N)
四.寫在最后
由于期末專業(yè)課較多，加上自己自控力不足，導(dǎo)致斷更了一段時間。寒假決定洗心革面，把斷更的博文都補起來。博主在寫博客過程中可能出現(xiàn)一些錯誤，望大家斧正，以及由任何問題可以在評論區(qū)或者私信與博主交流。希望大家寒假能有所收獲，一起卷起來！
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之復(fù)雜度篇的文章就介紹到這了,更多相關(guān)Java 復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
使用Spring @DependsOn控制bean加載順序的實例
這篇文章主要介紹了使用Spring @DependsOn控制bean加載順序的實例講解，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-07-07
下面小編就為大家?guī)硪黄獪\談Java中注解Annotation的定義、使用、解析。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-04-04
這篇文章主要介紹了IDEA簡單實現(xiàn)登錄注冊頁面,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12
詳解MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入
這篇文章主要介紹了MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入的相關(guān)知識，需要的朋友一起學(xué)習(xí)吧2016-01-01
Spring Cloud Feign接口返回流的實現(xiàn)
這篇文章主要介紹了Spring Cloud Feign接口返回流的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10
Java微信公眾平臺開發(fā)（6） 微信開發(fā)中的token獲取
這篇文章主要為大家詳細介紹了Java微信公眾平臺開發(fā)第六步，微信開發(fā)中的token獲取，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-04-04
我們無論是在聊天還是在留言時，都有一些信息不希望別人看到。那么如果過濾這些關(guān)鍵詞呢？下面小編給大家分享JavaEE Filter敏感詞過濾的方法實例詳解，感興趣的朋友一起學(xué)習(xí)吧2016-05-05
java split結(jié)果去除空字符串的方法實現(xiàn)
在Java開發(fā)中,我們經(jīng)常需要對字符串進行分割操作,本文主要介紹了java split結(jié)果去除空字符串的方法實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2023-10-10
這篇文章主要介紹了java實現(xiàn)投票程序設(shè)計，具有一定的參考價值，感興趣的小伙伴們可以參考一下2015-12-12
詳解Java中while和do-while循環(huán)、break的使用
本文介紹了循環(huán)結(jié)構(gòu)語句while和do-while循環(huán)、break的使用，while循環(huán)語句通過流程圖和語法語句結(jié)合一個求1~10的整數(shù)和的例子來幫助大家理解while循環(huán)的用法，感興趣的朋友跟隨小編來看看吧2020-11-11