比比看！Java時間和空間的複雜度演算法，3分鐘你能學會哪個？

今日分享開始啦，請大家多多指教~

前言

1。在平常我們所說的時間複雜度一般說的都是演算法的最壞情況；

2。時間複雜度度是一個函式，這個函式只能大致估一下這個演算法的時間複雜度；

3。空間複雜度是個演算法在執行過程中額外佔用儲存空間大小的量度。

一、演算法效率

演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間複雜度，而空間效率被稱作空間複雜度。 時間複雜度主要衡量的是一個演算法的執行速度，而空間複雜度主要衡量一個演算法所需要的額外空間。

二、時間複雜度

1。時間複雜度的概念

在計算機科學中，演算法的時間複雜度是一個函式，它定量描述了該演算法的執行時間。

演算法中的基本操作的執行次數，為演算法的時間複雜度。從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道。但是我們需要每個演算法都上機測試嗎？是可以都上機測試，但是這很麻煩，所以才有了時間複雜度這個分析方式。

一個演算法所花費的時間與其中語句的執行次數成正比例；

演算法中的基本操作的執行次數，為演算法的時間複雜度。

2。大O的漸進表示法

實際中我們計算時間複雜度時，我們其實並不一定要計算精確的執行次數，而只需要大概執行次數，那麼這裡我們使用大O的漸進表示法。

大O符號（Big O notation）：是用於描述函式漸進行為的數學符號

(1)推導大O階方法

用常數1取代執行時間中的所有加法常數。

在修改後的執行次數函式中，只保留最高階項。

如果最高階項存在且不是1，則去除與這個專案相乘的常數。得到的結果就是大O階

程式碼如下（示例）：

所以func方法的執行次數為 1+N2+2*N+1+10

我看到func的執行次數，如果當我們的N非常大時，假設N = 100，那麼這裡的+1和+10是不是可以忽略了，因為1002=10000，在一萬面前+1和+10可以說是微乎其微了，所以+1和+10沒什麼區別。

這就用到了前面說了推導大O階方法。

用常數1取代執行時間中的所有加法常數。

就變成了 1+N2+2*N+1+1；

再來看

在修改後的執行次數函式中，只保留最高階項。

簡化後 N2

如果最高階項存在且不是1，則去除與這個專案相乘的常數。得到的結果就是大O階。

這裡我們的最高階項是2，但前面沒有常數所以沒必要去除，如果N2前面還有個2就是2N2就要去除2變成 N2；

所以使用大O的漸進表示法以後，Func的時間複雜度為 O（N2）。

透過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明瞭地表示出了執行次數。時間複雜度是一個函式，只能大致估一下這個演算法的時間複雜度。

3。時間複雜度的三種情況

另外有些演算法的時間複雜度存在最好、平均和最壞情況。

(1) 最壞情況

最壞情況：任意輸入規模的最大執行次數（上界） 也就是 O（N）；

這裡的N代表的是問題的規模；

(2)最好情況

任意輸入規模的最小執行次數（下界） 也就是 O（1）；

(3)平均情況

任意輸入規模的期望執行次數；

注意：這裡的平均情況並不是最好和最壞情況相加的平均值，而是我們期望執行的次數，有時候平均情況可能和最好或者是最壞情況一樣。

在平常我們所說的時間複雜度一般說的都是演算法的最壞情況。

4。常見時間複雜度計算舉例

1.例子

示例1：

1+2*N+1+10 透過推導大O階方法後：時間複雜度為 O（N）；

示例2：

時間複雜度為：O（M+N）；

示例3：

這裡的時間複雜度為 O（1），因為傳進來的N並沒有使用；

2.氣泡排序時間複雜度

示例4：

這是一個氣泡排序，我們來求一下它的最好最壞和平均情況的時間複雜度。

最好：O（N）

最壞：O（N2）

平均：O（N）

這是一個經過最佳化後的氣泡排序，最好的情況就是該組資料已經是有序的了，所以只需走一遍就好了，也是是O（N）。

而最壞的情況就把陣列全部遍歷了一遍就是 N2；

我們前面說過平均情況就是我們個期望的情況，我們期望的當然就是O（N）。

3.二分查詢的時間複雜度

我們知道求時間複雜度一般求的都是最壞的情況，二分查詢只有當我們找最旁邊那兩個個數時才是最壞情況，我們就假設我們要找的就是最邊邊的那個數。

所以二分查詢的時間複雜度為

O(log2N)。

4.遞迴的時間複雜度

遞迴的時間複雜度 = 遞迴的次數*每次遞迴執行的操作的次數；

示例1：

這裡的的遞迴次數為 N 次，這裡沒有迴圈，每次執行的是一個三目運算子相當於1次。所以為 N+1次，時間複雜度就是 O（N）。

示例2：

這是一個遞迴實現的斐波那契數列；

斐波那契數列的遞迴次數其實就是一個等比數列求和，最後的執行次數為 （2n） - 1，透過透過推導大O階方法最後的時間複雜度為

O(2N)。

時間複雜度只是一個大概的，當數字足夠大時這裡缺失的部分並不影響我們時間複雜度的計算。

三、空間複雜度

1。空間複雜度概念

空間複雜度是對一個演算法在執行過程中臨時（額外）佔用儲存空間大小的量度；

佔用儲存空間大小的量度 。

空間複雜度不是程式佔用了多少bytes的空間，因為這個也沒太大意義，所以空間複雜度算的是變數的個數。

空間複雜度計算規則基本跟實踐複雜度類似，也使用大O漸進表示法。

2。空間複雜度的計算

(1) 氣泡排序

這個氣泡排序的空間複雜度為 O（1）；

為什麼呢？因為空間複雜度是為了解決一個問題額外申請了其他變數，這裡的array陣列並不是額外的它是必須的，但這裡的 sorted 是額外申請的，它每迴圈一次就定一次為什麼不是O（N）呢？因為每迴圈一次這個變數是不是不要了呢？所以來來回回就是這一個變數。

(2) 斐波那契數列

這裡的空間複雜度為

O(N)；

這裡為了求第1~N的斐波那契數列的程式碼，為了解決這個問題申請了一個額外的陣列的空間，空間大小為 N+1。因為1是常數項，所以這個程式碼的空間複雜度為 O（N）。

(3)遞迴

這是一個求階層的遞迴，他的空間複雜度為

O(N)；

因為遞迴在遞的過程中，每遞一次都會都會建立一個臨時變數。

小結

在計算機發展的早期，計算機的儲存容量很小，所以對空間複雜度很是在乎。但是經過計算機行業的迅速發展，計算機的儲存容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個演算法的空間複雜度。因為現在的記憶體不像以前那麼貴，所以經常聽到過犧牲空間來換取時間的說法。

今日份分享已結束，請大家多多包涵和指點！