??博客主頁(yè)：愛(ài)敲代碼的小楊.
?專欄：《Java SE語(yǔ)法》
??感謝大家點(diǎn)贊????收藏?評(píng)論???，您的三連就是我持續(xù)更新的動(dòng)力??
??小楊水平有限，歡迎各位大佬指點(diǎn)，相互學(xué)習(xí)進(jìn)步！
時(shí)間和空間復(fù)雜度
1. 算法效率
算法效率分為兩種：第一種是時(shí)間效率；第二種是空間效率。時(shí)間效率又稱為時(shí)間復(fù)雜度，而空間效率又稱為空間復(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)缃癫恍枰貏e關(guān)注空間復(fù)雜度。
2. 時(shí)間復(fù)雜度
2.1 時(shí)間復(fù)雜度的概念
時(shí)間復(fù)雜度的定義：算法的時(shí)間復(fù)雜度是一個(gè)數(shù)學(xué)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。應(yīng)該算法所花費(fèi)的時(shí)間與其中語(yǔ)句執(zhí)行次數(shù)成正比。算法的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
2.2 大O漸進(jìn)表示法
// 請(qǐng)計(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);
}
Func1 執(zhí)行的基本次數(shù)：F(N) = N2 +2 * N + 10
- N = 10, F(N) = 130;
- N = 100, F(N) = 10210;
- N = 1000, F(N) = 1002010;
在實(shí)際上我們計(jì)算機(jī)時(shí)間復(fù)雜度的，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么我們使用大O漸進(jìn)表示法。
大O符號(hào)：是用于描述函數(shù)的漸進(jìn)行為的數(shù)學(xué)符號(hào)。
2.3 推導(dǎo)大O階方法
- 用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
- 在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
- 如果最高階存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。
使用大O的漸進(jìn)表示法以后，Func1的時(shí)間復(fù)雜度為：O(N2)
- N = 10, F(N) = 100
- N = 100 ,F(N) = 1000
- N = 1000, F(N) = 1000000
通過(guò)上面我們會(huì)發(fā)現(xiàn)大0漸進(jìn)表示法去掉了那些對(duì)結(jié)果影響不大的項(xiàng)。簡(jiǎn)潔明了的表示出了執(zhí)行次數(shù)。
另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：
-
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)（上界）
-
平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
-
最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)（下界）
在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況。
2.4 常見(jiàn)的時(shí)間復(fù)雜度
【例子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);
}
/*
func2基本操作執(zhí)行次數(shù) 2N + 10次
時(shí)間復(fù)雜度：O(N)
*/
【例子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);
}
/*
func3基本操作次數(shù) M + N 次
時(shí)間復(fù)雜度：0(M + N)
*/
【例子3】：
// 計(jì)算func4的時(shí)間復(fù)雜度？
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}
/*
func4基本操作次數(shù) 100次
時(shí)間復(fù)雜度：O(1)
*/
【例子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;
}
}
/*
bubbleSort的最好情況為N次，最壞情況為(N * (N - 1) / 2)
時(shí)間復(fù)雜度為：O(N ^ 2)
*/
【例子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;
else
return mid;
}
return -1;
}
/*
binarySearch的時(shí)間復(fù)雜度:O(longN)
*/
【例子6】：
// 計(jì)算階乘遞歸factorial的時(shí)間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}
/*
factorial基本操作遞歸了N次
時(shí)間復(fù)雜度為O(N)。
*/
【例子7】：
// 計(jì)算斐波那契遞歸?bonacci的時(shí)間復(fù)雜度？
int ?bonacci(int N) {
return N < 2 ? N : ?bonacci(N-1)+?bonacci(N-2);
}
/*
?bonacci基本操作遞歸了2^N次，時(shí)間復(fù)雜度為O(2^N)
*/
3. 空間復(fù)雜度
空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度 。空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒(méi)太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。空間復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似，也使用大O漸進(jìn)表示法。
【例子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;
}
}
}
/*
bubbleSort使用了常數(shù)個(gè)額外空間
空間復(fù)雜度為 O(1)
*/
【例子2】：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-809504.html
// 計(jì)算?bonacci的空間復(fù)雜度？
int[] ?bonacci(int n) {
long[] ?bArray = new long[n + 1];
?bArray[0] = 0;
?bArray[1] = 1;
for (int i = 2; i <= n ; i++) {
?bArray[i] = ?bArray[i - 1] + ?bArray [i - 2];
}
return ?bArray;
}
/*
?bonacci動(dòng)態(tài)開(kāi)辟了N個(gè)空間
空間復(fù)雜度為 O(N)
*/
【例子3】：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-809504.html
// 計(jì)算階乘遞歸Factorial的空間復(fù)雜度？
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}
/*
factorial遞歸調(diào)用了N次，開(kāi)辟了N個(gè)棧幀，每個(gè)棧幀使用了常數(shù)個(gè)空間。
空間復(fù)雜度為O(N)
*/
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】1.時(shí)間復(fù)雜度和空間復(fù)雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
