系列文章目錄
文章目錄
- 系列文章目錄
- 前言
- 一、時間復雜度
- 1.時間復雜度的概念
- 2.大O的漸進表示法
- 3.時間復雜度經典題目
- 二、空間復雜度
- 1.空間復雜度的概念
- 2.空間復雜度經典題目
- 總結
前言
演算法效率分析分為兩種：第一種是時間效率，第二種是空間效率，時間效率被稱為時間復雜度，而空間效率被稱作空間復雜度， 時間復雜度主要衡量的是一個演算法的運行速度，而空間復雜度主要衡量一個演算法所需要的額外空間，在計算機發展的早期，計算機的存盤容量很小，所以對空間復雜度很是在乎，但是經過計算機行業的迅速發展，計算機的存盤容量已經達到了很高的程度，所以我們如今已經不需要再特別關注一個演算法的空間復雜度，
一、時間復雜度
1.時間復雜度的概念
時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，
2.大O的漸進表示法
計算下面代碼的時間復雜度:
Func1 執行的基本操作次數 ：
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
實際中我們計算時間復雜度時，我們其實并不一定要計算精確的執行次數，而只需要大概執行次數，那么這里我們使用大O的漸進表示法，
大O符號（Big O notation）：是用于描述函式漸進行為的數學符號，
推導大O階方法：
1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，
使用大O的漸進表示法以后，Func1的時間復雜度為：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發現大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數，
另外有些演算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)
3.時間復雜度經典題目
題目1:
此時演算法的執行次數是2N+M次，通過推導大O的漸進表示法時間復雜度是O（N+M），
題目2：
此時演算法的執行次數是M+N次，有兩個未知數，時間復雜度是O（M+N），
題目3:
此時演算法的執行次數是100次，由于是常數項，所以時間復雜度是O（1），
題目四：
strchr是在一個字串中查找一個字符，查找次數最好O（1），最壞O（N），根據大O的漸進表示法所以為O（N），
題目5:
因為比較的數字是n-1,n-2,n-3…3,2,1反過來就是1,2，3，…，n-3，n-2,n-1規律就是一個等引數列根據等引數列求和公式(n^2+n)/2，那么根據大O的漸進表示法就是O（N方），
題目6:
在一個有序的陣列中一直二分直到找到要找的那個數字,那么n/2/2/2…=1,那么就可以變換為2^x=n,那么x就是log以2為底，n的次方，時間復雜度就是O(logN)，
題目7:
這個題目求N階層,那么演算法的執行次數就是N，時間復雜度就是O（N），
題目8:
由上圖知道演算法的執行次數為1,2,4,8…是一個等比數列，所以根據大O的漸進表示法時間復雜度是O（2^N），
二、空間復雜度
1.空間復雜度的概念
空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，空間復雜度不是程式占用了多少bytes的空間，因為這個也沒太大意義，所以空間復雜度算的是變數的個數，空間復雜度計算規則基本跟實踐復雜度類似，也使用大O漸進表示法，
2.空間復雜度經典題目
題目1：
這里使用的常數個空間，所以空間復雜度是O（1），
題目2:
這里動態開辟了n+1個空間，所以空間復雜度是O(N)，
題目三:
這里遞回每次呼叫一次函式，就會開辟一次堆疊幀，每個堆疊幀使用了常數個空間，所以空間復雜度為O(N)
總結
以上就是今天要講的內容，本文僅僅簡單介紹了時間復雜度和空間復雜度使用，對于演算法運行時間的快慢和所需要耗費的時間以這兩種復雜度來衡量，對我們以后的做題優解有十分大的幫助，我們務必掌握，另外還有，如果上述有任何問題，請懂哥指教，不過沒關系，主要是自己能堅持，更希望有一起學習的同學可以幫我指正，但是如果可以請溫柔一點跟我講，愛與和平是永遠的主題，愛各位了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282084.html
標籤：AI