Java數(shù)據(jù)結(jié)構(gòu)通關(guān)時間復(fù)雜度和空間復(fù)雜度
算法效率
算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間復(fù)雜度，而空間效率被 稱作空間復(fù)雜度。 時間復(fù)雜度主要衡量的是一個算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個算法所需要的額 外空間,在計(jì)算機(jī)發(fā)展的早期,計(jì)算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎（以前是以時間換空間).但是經(jīng)過計(jì)算機(jī)行業(yè)的 迅速發(fā)展，計(jì)算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù) 雜度（現(xiàn)在是以空間換時間）。
時間復(fù)雜度
時間復(fù)雜度的定義：在計(jì)算機(jī)科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運(yùn)行時間。一個算法執(zhí)行所耗費(fèi)的時間，從理論上說，是不能算出來的，只有你把你的程序放在機(jī)器上跑起來，才能知道。但 是我們需要每個算法都上機(jī)測試嗎？是可以都上機(jī)測試，但是這很麻煩所以才有了時間復(fù)雜度這個分析方 式。一個算法所花費(fèi)的時間與其中語句的執(zhí)行次數(shù)成正比例， 算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù) 雜度。
實(shí)際中我們計(jì)算時間復(fù)雜度時，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要 大概執(zhí)行次數(shù)，那么這里我們使用大 O 的漸進(jìn)表示法。
大 O 符號（ Big O notation ）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號。
推導(dǎo)大 O 階方法：
1 、用常數(shù) 1 取代運(yùn)行時間中的所有加法常數(shù)。
2 、在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
3 、如果最高階項(xiàng)存在且不是 1 ，則去除與這個項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大 O 階
來看些例子：
// 請計(jì)算一下func1基本操作執(zhí)行了多少次？
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);
}
通過上面我們會發(fā)現(xiàn)大 O 的漸進(jìn)表示法 去掉了那些對結(jié)果影響不大的項(xiàng) ，簡潔明了的表示出了執(zhí)行次數(shù)。
另外有些算法的時間復(fù)雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù) ( 上界 )
平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù) ( 下界 )
例如：在一個長度為 N 數(shù)組中搜索一個數(shù)據(jù) x
最好情況： 1 次找到
最壞情況： N 次找到
平均情況： N/2 次找到
在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以數(shù)組中搜索數(shù)據(jù)時間復(fù)雜度為 O(N)
例子二
// 計(jì)算func2的時間復(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ì)算func3的時間復(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ì)算func4的時間復(fù)雜度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++; }
System.out.println(count);
}
例子五
// 計(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;
}
}
}
例子六
// 計(jì)算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; }
例子七
// 計(jì)算階乘遞歸factorial的時間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N; }
空間復(fù)雜度
空間復(fù)雜度是對一個算法在運(yùn)行過程中 臨時占用存儲空間大小的量度 ?？臻g復(fù)雜度不是程序占用了多少 bytes的空間，因?yàn)檫@個也沒太大意義，所以空間復(fù)雜度算的是變量的個數(shù)（額外變量個數(shù)）。空間復(fù)雜度計(jì)算規(guī)則基本跟時間復(fù)雜度 類似。也使用 大 O 漸進(jìn)表示法 。
例子一
// 計(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;
}
}
}
例子二
// 計(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;
}
例子三
// 計(jì)算階乘遞歸Factorial的空間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
小結(jié)
這篇文章講的都是一些簡單的時間復(fù)雜度和空間復(fù)雜度的計(jì)算，如果有什么不正確的地方，歡迎大家指出來。
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)通關(guān)時間復(fù)雜度和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)Java時間復(fù)雜度 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Mybatis Plus框架項(xiàng)目落地實(shí)踐分析總結(jié)
這篇文章主要為大家介紹了Mybatis Plus框架項(xiàng)目落地實(shí)踐分析總結(jié)，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-03-03
這篇文章主要介紹了如何解決springboot自動重啟問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-09-09
這篇文章主要介紹了Java中如何獲取文件的上級目錄問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
解決springboot項(xiàng)目啟動失敗Could not initialize class&
這篇文章主要介紹了解決springboot項(xiàng)目啟動失敗Could not initialize class com.fasterxml.jackson.databind.ObjectMapper問題,具有很好的參考價(jià)值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
解決springboot利用ConfigurationProperties注解配置數(shù)據(jù)源無法讀取配置信息問題
今天在學(xué)習(xí)springboot利用ConfigurationProperties注解配置數(shù)據(jù)源的使用遇到一個問題無法讀取配置信息，發(fā)現(xiàn)全部為null，糾結(jié)是哪里出了問題呢，今天一番思考，問題根源找到，下面把我的解決方案分享到腳本之家平臺，感興趣的朋友一起看看吧2021-05-05
java代碼抓取網(wǎng)頁郵箱的實(shí)現(xiàn)方法
下面小編就為大家?guī)硪黄猨ava代碼抓取網(wǎng)頁郵箱的實(shí)現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
這篇文章主要介紹了java中的傳值與傳引用實(shí)現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-10-10
這篇文章主要為大家詳細(xì)介紹了JAVA的觀察者模式，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-08-08
這篇文章主要介紹了java定義受限制的類型參數(shù)操作，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08
Java實(shí)現(xiàn)多個數(shù)組間的排列組合
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)多個數(shù)組間的排列組合，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-02-02