算法的時間複雜度和空間複雜度

清晨白米稀飯. 2022-01-08 03:17:53 阅读数:536

算法

一、算法效率

1.1如何衡量一個算法的好壞

如何衡量一個算法的好壞呢?
算法在編寫成可執行程序後,運行時需要耗費時間資源和空間(內存)資源 。因此衡量一個算法的好壞,一般是從時間和空間兩個維度來衡量的,即時間複雜度和空間複雜度

1.2 算法的複雜度

時間複雜度主要衡量一個算法的運行快慢,而空間複雜度主要衡量一個算法運行所需要的額外空間。
在計算機發展的早期,計算機的存儲容量很小。所以對空間複雜度很是在乎。但是經過計算機行業的迅速發展,計算機的存儲容量已經達到了很高的程度。所以我們如今已經不需要再特別關注一個算法的空間複雜度。

二、時間複雜度

2.1時間複雜度的概念

那什麼是時間複雜呢?
在計算機科學中,算法的時間複雜度是一個函數,它定量描述了該算法的運行時間。但是對於不同的運行系統來說,同一個程序,運行時間是不同的。所以才有了時間複雜度這個分析方式。一個算法所花費的時間與其中語句的執行次數成正比例,算法中的基本操作的執行次數,為算法的時間複雜度
既:找到某條基本語句與問題規模N之間的數學錶達式,就是算出了該算法的時間複雜度。
如下代碼:

// 請計算一下Func1中++count語句總共執行了多少次?
void Func1(int N)
{

int count = 0;
for (int i = 0; i < N ; ++ i)
{

for (int j = 0; j < N ; ++ j)
{

++count;
}
}
for (int k = 0; k < 2 * N ; ++ k)
{

++count;
}
int M = 10;
while (M--)
{

++count;
}
printf("%d\n", count);
}

Func1 執行的基本操作次數 :
在這裏插入圖片描述
但是實際中我們計算時間複雜度時,我們其實並不一定要計算精確的執行次數,而只需要大概執行次數,那麼這裏我們使用大O的漸進錶示法。

2.2 大O的漸進錶示法

大O符號(Big O notation):是用於描述函數漸進行為的數學符號。
推導大O階方法:

1、用常數1取代運行時間中的所有加法常數。
2、在修改後的運行次數函數中,只保留最高階項。
3、如果最高階項存在且不是1,則去除與這個項目相乘的常數。得到的結果就是大O階。

使用大O的漸進錶示法以後,Func1的時間複雜度為:O(N^2)

通過上面我們會發現大O的漸進錶示法去掉了那些對結果影響不大的項,簡潔明了的錶示出了執行次數。
另外有些算法的時間複雜度存在最好、平均和最壞情况:
最壞情况:任意輸入規模的最大運行次數(上界)
平均情况:任意輸入規模的期望運行次數
最好情况:任意輸入規模的最小運行次數(下界)
例如:在一個長度為N數組中搜索一個數據x
最好情况:1次找到
最壞情况:N次找到
平均情况:N/2次找到
在實際中一般情况關注的是算法的最壞運行情况,所以數組中搜索數據時間複雜度為O(N)

三、空間複雜度

空間複雜度也是一個函數錶達式,是對一個算法在運行過程中臨時占用存儲空間大小的量度 。
空間複雜度不是程序占用了多少bytes的空間,因為這個也沒太大意義,所以空間複雜度算的是變量的個數。
空間複雜度計算規則基本跟實踐複雜度類似,也使用大O漸進錶示法。
注意:函數運行時所需要的棧空間(存儲參數、局部變量、一些寄存器信息等)在編譯期間已經確定好了,因此空間複雜度主要通過函數在運行時候顯式申請的額外空間來確定。

四、常見複雜度對比

一般算法常見的複雜度如下:
在這裏插入圖片描述

版权声明:本文为[清晨白米稀飯.]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080317528664.html