Java 精煉解讀時間複雜度與空間複雜度

前言：

所謂的複雜度就是衡量演演算法的效率，衡量算髮效率又分為兩種，一種叫做時間複雜度，一種叫做空間複雜度。

一、演演算法效率

演演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。時間效率被稱為時間複雜度，而空間效率被 稱作空間複雜度。 時間複雜度主要衡量的是一個演演算法的執行速度，而空間複雜度主要衡量一個演演算法所需要的額 外空間，在計算機發展的早期，計算機的儲存容量很小。所以對空間複雜度很是在乎。但是經過計算機行業的 迅速發展，計算機的儲存容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個演演算法的空間復 雜度。

二、時間複雜度

1.時間複雜度概念

一個演演算法所花費的時間與其中語句的執行次數成正比例，演演算法中的基本操作的執行次數，為演演算法的時間復 雜度。也就是說當我們拿到一個程式碼，來看這個程式碼的時間複雜度的時候，主要是去找這個程式碼當中執行語句次數最多的程式碼執行了多少次。

2.大O的漸進表示法

看圖分析：

當N的值越來越大，2N和10的值就可以忽略不記了。 

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

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

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

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

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

通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明瞭的表示出了執行次數。

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

最壞情況：任意輸入規模的最大執行次數(上界)

平均情況：任意輸入規模的期望執行次數

最好情況：任意輸入規模的最小執行次數(下界) 

例如：在一個長度為N陣列中搜尋一個資料x

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到 

在實際中一般情況關注的是演演算法的最壞執行情況，所以陣列中搜尋資料時間複雜度為O(N)

計算時間複雜度  

例題1：

基本操作執行了2N+10次，通過推導大O階方法知道，時間複雜度為 O(N)

例題2：

基本操作執行了M+N次，有兩個未知數M和N，時間複雜度為 O(N+M)

例題3：

基本操作執行了100次，通過推導大O階方法，時間複雜度為 O(1)

例題4：計算氣泡排序的時間複雜度

基本操作執行最好N次，最壞執行了(N*(N-1))/2次，通過推導大O階方法+時間複雜度一般看最壞， 時間複雜度為 O(N^2

例題5：二分查詢的時間複雜度

基本操作執行最好1次，最壞O(logN)次，時間複雜度為 O(logN) ps：logN在演演算法分析中表示是底數 為2，對數為N。有些地方會寫成lgN。（建議通過摺紙查詢的方式講解logN是怎麼計算出來的）(因為二 分查詢每次排除掉一半的不適合值,一次二分剩下：n/2 兩次二分剩下：n/2/2 = n/4)

例題6：計算階乘遞迴的時間複雜度

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

通過計算分析發現基本操作遞迴了N次，時間複雜度為O(N)。

例題7：計算斐波那契遞迴的時間複雜度

通過計算分析發現基本操作遞迴了2^N次，時間複雜度為O(2^N)。

規律： 

 2^0+2^1+2^2+2^3……2^(n-(n-1))

等比數列求和

 a1就代表第一項，q是等比就是2，1(1-2^n)/-1,相當於2^n+1,所以時間複雜度為O(2^n)

三、空間複雜度 

空間複雜度是對一個演演算法在執行過程中臨時佔用儲存空間大小的量度 。空間複雜度不是程式佔用了多少bytes 的空間，因為這個也沒太大意義，所以空間複雜度算的是變數的個數。空間複雜度計算規則基本跟實踐複雜度 類似，也使用大O漸進表示法。

 例題1：計算氣泡排序的空間複雜度

使用了常數個額外空間，所以空間複雜度為 O(1)

 例題2：計算斐波那契的空間複雜度

動態開闢了N個空間，空間複雜度為 O(N)

例題3：計算階乘遞迴的空間複雜度

  遞迴呼叫了N次，開闢了N個棧幀，每個棧幀使用了常數個空間。空間複雜度為O(N)

總結：

本文簡單介紹了什麼是時間複雜度、空間複雜度，通過簡單例題的方式加深對陣列的理解。上述就是今天的內容，有任何疑問的話可以隨時私信我，文章哪裡出現了問題我都會積極改正，也希望大家能更快的掌握自己想要的知識，讓我們一起加油！！！！！

到此這篇關於Java 精煉解讀時間複雜度與空間複雜度的文章就介紹到這了,更多相關Java 時間複雜度內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！