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詳解MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入
這篇文章主要介紹了MyBatis直接執(zhí)行SQL查詢及數(shù)據(jù)批量插入的相關(guān)知識,需要的朋友一起學(xué)習(xí)吧2016-01-01Spring Cloud Feign接口返回流的實現(xiàn)
這篇文章主要介紹了Spring Cloud Feign接口返回流的實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-10-10Java微信公眾平臺開發(fā)(6) 微信開發(fā)中的token獲取
這篇文章主要為大家詳細介紹了Java微信公眾平臺開發(fā)第六步,微信開發(fā)中的token獲取,具有一定的參考價值,感興趣的小伙伴們可以參考一下2017-04-04java split結(jié)果去除空字符串的方法實現(xiàn)
在Java開發(fā)中,我們經(jīng)常需要對字符串進行分割操作,本文主要介紹了java split結(jié)果去除空字符串的方法實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2023-10-10詳解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