一、算法效率
算法效率分析分為兩種：第一種是時(shí)間效率，第二種是空間效率。時(shí)間效率被稱(chēng)為時(shí)間復(fù)雜度，而空間效率被稱(chēng)作空間復(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)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。因?yàn)楝F(xiàn)在的內(nèi)存不像以前那么貴，所以經(jīng)常聽(tīng)到過(guò)犧牲空間來(lái)?yè)Q取時(shí)間的說(shuō)法
二、時(shí)間復(fù)雜度
2.1 時(shí)間復(fù)雜度的概念
在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。
算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。從理論上說(shuō)，是不能算出來(lái)的，只有你把你的程序放在機(jī)器上跑起來(lái)，才能知道。但是我們需要每個(gè)算法都上機(jī)測(cè)試嗎？是可以都上機(jī)測(cè)試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。
一個(gè)算法所花費(fèi)的時(shí)間與其中語(yǔ)句的執(zhí)行次數(shù)成正比例，
算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
2.2 大O的漸進(jìn)表示法
實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法
大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)
(1)推導(dǎo)大O階方法
用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階
代碼如下（示例）：
void func(int N){
int count = 0;//執(zhí)行1次
for (int i = 0; i < N ; i++) {//執(zhí)行N*N次
for (int j = 0; j < N ; j++) {
count++;
}
}
for (int k = 0; k < 2 * N ; k++) {//執(zhí)行2*N次
count++;
}
int M = 10;//執(zhí)行1次
while ((M--) > 0) {//執(zhí)行10次
count++;
}
System.out.println(count);
}
所以func方法的執(zhí)行次數(shù)為 1+N2+2*N+1+10
我看到func的執(zhí)行次數(shù)，如果當(dāng)我們的N非常大時(shí)，假設(shè)N = 100，那么這里的+1和+10是不是可以忽略了，因?yàn)?002=10000,在一萬(wàn)面前+1和+10可以說(shuō)是微乎其微了，所以+1和+10沒(méi)什么區(qū)別。
這就用到了前面說(shuō)了推導(dǎo)大O階方法，
用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
就變成了 1+N2+2*N+1+1
再來(lái)看
在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
簡(jiǎn)化后 N2
如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階
這里我們的最高階項(xiàng)是2，但前面沒(méi)有常數(shù)所以沒(méi)必要去除，如果N2前面還有個(gè)2就是2N2就要去除2變成 N2
所以使用大O的漸進(jìn)表示法以后，F(xiàn)unc的時(shí)間復(fù)雜度為 O(N2)
通過(guò)上面我們會(huì)發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對(duì)結(jié)果影響不大的項(xiàng)，簡(jiǎn)潔明了的表示出了執(zhí)行次數(shù)。時(shí)間復(fù)雜度是一個(gè)函數(shù)，只能大致估一下這個(gè)算法的時(shí)間復(fù)雜度。
2.3 時(shí)間復(fù)雜度的三種情況
另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況。
(1) 最壞情況
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界) 也就是 O(N)
這里的N代表的是問(wèn)題的規(guī)模
(2)最好情況
任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界) 也就是 O(1)
(3)平均情況
任意輸入規(guī)模的期望運(yùn)行次數(shù)
注意：這里的平均情況并不是最好和最壞情況相加的平均值，而是我們期望運(yùn)行的次數(shù)，有時(shí)候平均情況可能和最好或者是最壞情況一樣。
在平常我們所說(shuō)的時(shí)間復(fù)雜度一般說(shuō)的都是算法的最壞情況
2.4 常見(jiàn)時(shí)間復(fù)雜度計(jì)算舉例
2.4.1 例子
示例1：
void func2(int N) {
int count = 0;//1
for (int k = 0; k < 2 * N ; k++) { //2*N
count++;
}
int M = 10;//1
while ((M--) > 0) {//10
count++;
}
System.out.println(count);
}
1+2*N+1+10 通過(guò)推導(dǎo)大O階方法后:時(shí)間復(fù)雜度為 O(N)
示例2：
void func3(int N, int M) {
int count = 0;//常數(shù)可以不加
for (int k = 0; k < M; k++) {//M
count++;
}
for (int k = 0; k < N ; k++) {//N
count++;
}
System.out.println(count);
}
時(shí)間復(fù)雜度為：O(M+N)
示例3：
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {//用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)
count++;
}
System.out.println(count);
}這里的時(shí)間復(fù)雜度為 O(1),因?yàn)閭鬟M(jìn)來(lái)的N并沒(méi)有使用
2.4.2 冒泡排序時(shí)間復(fù)雜度
示例4：
這是一個(gè)冒泡排序，我們來(lái)求一下它的最好最壞和平均情況的時(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;
}
}
}
最好：O(N)
最壞：O(N2)
平均：O(N)
這是一個(gè)經(jīng)過(guò)優(yōu)化后的冒泡排序，最好的情況就是該組數(shù)據(jù)已經(jīng)是有序的了，所以只需走一遍就好了，也是是O(N).
而最壞的情況就把數(shù)組全部遍歷了一遍就是 N2
我們前面說(shuō)過(guò)平均情況就是我么個(gè)期望的情況，我們期望的當(dāng)然就是O(N)
2.4.3 二分查找的時(shí)間復(fù)雜度
我們知道求時(shí)間復(fù)雜度一般求的都是最壞的情況，二分查找只有當(dāng)我們找最旁邊那兩個(gè)個(gè)數(shù)時(shí)才是最壞情況，我們就假設(shè)我們要找的就是最邊邊的那個(gè)數(shù)。
public static int binarySearch(int[] arr,int x){
int left = 0;
int right = arr.length-1;
int mid = 0;//中間下標(biāo)
while(left <= right){
mid = left+(right-left)/2;
if(arr[mid] > x){
right = mid - 1;
}else if(arr[mid] < x){
left = mid+1;
}else{
return mid;
}
}
return -1;
}
所以二分查找的時(shí)間復(fù)雜度為 O(log2N)
2.4.4 遞歸的時(shí)間復(fù)雜度
遞歸的時(shí)間復(fù)雜度 = 遞歸的次數(shù)*每次遞歸執(zhí)行的操作的次數(shù)
示例1：
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}這里的的遞歸次數(shù)為 N 次，這里沒(méi)有循環(huán)，每次執(zhí)行的是一個(gè)三目操作符相當(dāng)于1次。所以為 N+1次，時(shí)間復(fù)雜度就是 O(N)。
示例2：
這是一個(gè)遞歸實(shí)現(xiàn)的斐波那契數(shù)列
public static int fib(int n){
if(n==1||n==2){
return 1;
}else{
return fib(n-1)+fib(n-2);
}
}斐波那契數(shù)列的遞歸次數(shù)其實(shí)就是一個(gè)等比數(shù)列求和，最后的執(zhí)行次數(shù)為 (2n) - 1,通過(guò)通過(guò)推導(dǎo)大O階方法最后的時(shí)間復(fù)雜度為 O(2N)
時(shí)間復(fù)雜度只是一個(gè)大概的，當(dāng)數(shù)字足夠大時(shí)這里缺失的部分并不影響我們時(shí)間復(fù)雜度的計(jì)算。
三、空間復(fù)雜度
3.1 空間復(fù)雜度概念
空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)(額外)占用存儲(chǔ)空間大小的量度
占用存儲(chǔ)空間大小的量度 。
空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒(méi)太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。
空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類(lèi)似，也使用大O漸進(jìn)表示法
3.2 空間復(fù)雜度的計(jì)算
(1) 冒泡排序
這個(gè)冒泡排序的空間復(fù)雜度為 O(1)
為什么呢？因?yàn)榭臻g復(fù)雜度是為了解決一個(gè)問(wèn)題額外申請(qǐng)了其他變量，這里的array數(shù)組并不是額外的它是必須的，但這里的 sorted 是額外申請(qǐng)的，它每循環(huán)一次就定一次為什么不是O(N)呢？因?yàn)槊垦h(huán)一次這個(gè)變量是不是不要了呢？所以來(lái)來(lái)回回就是這一個(gè)變量。
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) 斐波那契數(shù)列
這里的空間復(fù)雜度為 O(N)
這里為了求第1~N的斐波那契數(shù)列的代碼，為了解決這個(gè)問(wèn)題申請(qǐng)了一個(gè)額外的數(shù)組的空間，空間大小為 N+1。因?yàn)?是常數(shù)項(xiàng)，所以這個(gè)代碼的空間復(fù)雜度為 O(N)
public static long[] 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)遞歸
這是一個(gè)求階層的遞歸，他的空間復(fù)雜度為 O(N)
因?yàn)檫f歸在遞的過(guò)程中，每遞一次都會(huì)都會(huì)創(chuàng)建一個(gè)臨時(shí)變量。
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}四、總結(jié)
1.在平常我們所說(shuō)的時(shí)間復(fù)雜度一般說(shuō)的都是算法的最壞情況
2.時(shí)間復(fù)雜度度是一個(gè)函數(shù)，這個(gè)函數(shù)只能大致估一下這個(gè)算法的時(shí)間復(fù)雜度
3.空間復(fù)雜度是個(gè)算法在運(yùn)行過(guò)程中額外占用存儲(chǔ)空間大小的量度
關(guān)于算法的時(shí)間復(fù)雜度和空間復(fù)雜度的介紹，并通過(guò)Java編寫(xiě)算法計(jì)算復(fù)雜度的內(nèi)容就介紹到此結(jié)束了，如果你還想要了解更多關(guān)于Java語(yǔ)言相關(guān)的算法內(nèi)容，請(qǐng)多多關(guān)注W3Cschool相關(guān)內(nèi)容的文章。
