資料結構-時間複雜度和空間複雜度

如有錯誤，望不吝斧正！

文章目錄

• 算法時間複雜度
• • 推導大O階方法
  • • 常數階
    • 線性階
    • 對數階
    • 平方階
    • 常見時間複雜度
• 算法空間複雜度

算法時間複雜度

定義：在進行算法分析時，語句總的執行次數T(n)是關于問題模型n的函數，進而分析T(n)随n的變化情況并确定T(n)的數量級。算法的時間複雜度，也就是算法的時間量度，記作：T(n)=O(f(n))。它表示随問題規模n的增大，算法執行時間的增長率和f(n)的增長率相同，稱作算法的漸進時間複雜度，簡稱為時間複雜度。其中f(n)是問題規模n的某個函數。

這樣用大寫O()來展現算法時間複雜度的記法，成為大O記法。一般情況下，随着n的增大，T(n)增長最慢的算法為最優算法。

推導大O階方法

1. 用常數1取代運作時間中的所有加法常數
2. 在修改後的運作次數函數中，隻保留最高階項
3. 如果最高階項存在且不是1，則丢棄與這個項相乘的常數

常數階

通過高斯算法來推導：

int n = 100;
int r = (1 + n) * (n >> 1);
System.out.println(r);
           

不管 n 的數值是多少，這段代碼始終隻會執行3次。

與問題的大小無關（n的多少），執行時間恒定的算法，稱之為具有O(1)的時間複雜度，又叫常數階。

線性階

通過求100的階加來推導：

int n = 100,k = 0;
for (int i = 1; i <= n; i++) {
	k += i; //執行一次
}
System.out.println(k);
           

上面代碼循環的時間複雜度為O(n)，因為循環體中的代碼要執行n次。

對數階

int i = 1;
while(i<n)
{
    i = i * 2;
}
           

由于每次 i 乘以2後，就更接近n。可知x個2相乘後>=n退出循環，由 2ᕽ =n可得x=㏒₂ⁿ。是以這個循環的時間複雜度為O(㏒n)。

平方階

for (int i = 0; i < n; i++) {
	for (int j = 0; j < n; j++) {
		//時間複雜度為O(1)的程式步驟序列
	}
}
           

時間複雜度為：O(n²)

for (int i = 0; i < m; i++) {
	for (int j = 0; j < n; j++) {
		//時間複雜度為O(1)的程式步驟序列
	}
}
           

時間複雜度為：O(nm)

循環的時間複雜度等于循環體的複雜度乘以該循環運作的次數。

a:for (int i = 0; i < n; i++) {
	b:for (int j = i; j < n; j++) {
		//時間複雜度為O(1)的程式步驟序列
	}
}
           

推導過程：

i	循環執行次數
i=0	循環b執行n次
i=1	循環b執行n-1次
i=2	循環b執行n-2次
i=n-1	循環b執行1次

可得：n+(n-1)+(n-2)+1=（首項+尾項）*項數/2=（n+1）*n/2=n²/2+n/2

是以經過推導後最終可得：O(n²)

for (int i = 0; i < n; i++) {
	for (int j = 0; j < i; j++) {
		//時間複雜度為O(1)的程式步驟序列
	}
}
           

通過以上方式推導，可得：O(n²)

常見時間複雜度

執行次數函數	階	非正式術語	常見操作
12	O(1)	常數階	普通語句
2n+3	O(n)	線性階	循環
3n²+2n+1	O(n²)	平方階	雙層循環
5㏒₂ⁿ+20	O(㏒n)	對數階	二分政策
2n+3n㏒₂ⁿ+19	O(n㏒n)	n㏒n階	分治
6n³+2n²+3n+4	O(n³)	立方階	三層循環
2ⁿ	O(2ⁿ)	指數階	窮舉查找

常用的時間複雜度所耗費的時間從小到大依次是：

O(1) <O(㏒n) <O(n) <O(n㏒n)< O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

從O(n³)開始，過大的n都會使得結果變得不現實，是以不作讨論。

算法空間複雜度

算法的空間複雜度通過計算算法所需的存儲空間實作，算法空間複雜度的計算公式記作：S(n)=O(f(n)) ，其中，n為問題的規模，f(n)為語句關于n所占存儲空間的函數。

參考：

大話資料結構

https://www.zhihu.com/question/21387264