C語言算法的時(shí)間復(fù)雜度和空間復(fù)雜度
1.算法效率
1.1 如何衡量一個(gè)算法的好壞
如何衡量一個(gè)算法的好壞呢？比如對于以下斐波那契數(shù)列：
long long Fib(int N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}斐波那契數(shù)列的遞歸實(shí)現(xiàn)方式非常簡潔，但簡潔一定好嗎？那該如何衡量其好與壞呢？
1.2算法的復(fù)雜度
算法在編寫成可執(zhí)行程序后，運(yùn)行時(shí)需要耗費(fèi)時(shí)間資源和空間(內(nèi)存)資源 。因此衡量一個(gè)算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來衡量的，即時(shí)間復(fù)雜度和空間復(fù)雜度。
時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。在計(jì)算機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度。
2.時(shí)間復(fù)雜度
2.1 時(shí)間復(fù)雜度的概念
時(shí)間復(fù)雜度的定義：在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上說，是不能算出來的，只有你把你的程序放在機(jī)器上跑起來，才能知道。但是我們需要每個(gè)算法都上機(jī)測試嗎？是可以都上機(jī)測試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。
即：找到某條基本語句與問題規(guī)模N之間的數(shù)學(xué)表達(dá)式，就是算出了該算法的時(shí)間復(fù)雜度。
下面舉個(gè)例子：
請計(jì)算一下Func1中++count語句總共執(zhí)行了多少次？
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 執(zhí)行的基本操作次數(shù) ： F(N) = N^2 + 2*N + 10
代入數(shù)字計(jì)算一下：
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
可以發(fā)現(xiàn)當(dāng)N越來越大的時(shí)候，數(shù)字的大小主要取決于N^2了。
實(shí)際中我們計(jì)算時(shí)間復(fù)雜度時(shí)，我們其實(shí)并不一定要計(jì)算精確的執(zhí)行次數(shù)，而只需要大概執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法。
2.2 大O的漸進(jìn)表示法
大O符號（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號。
推導(dǎo)大O階方法：
- 1、用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
- 2、在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)。
- 3、如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)相乘的常數(shù)。得到的結(jié)果就是大O階。
使用大O的漸進(jìn)表示法以后，F(xiàn)unc1的時(shí)間復(fù)雜度為： O(N^2)
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通過上面我們會發(fā)現(xiàn)大O的漸進(jìn)表示法去掉了那些對結(jié)果影響不大的項(xiàng)，簡潔明了的表示出了執(zhí)行次數(shù)。
另外有些算法的時(shí)間復(fù)雜度存在最好、平均和最壞情況：
- 最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
- 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
- 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界)
例如：在一個(gè)長度為N數(shù)組中搜索一個(gè)數(shù)據(jù)x
- 最好情況：1次找到
- 最壞情況：N次找到
- 平均情況：N/2次找到
在實(shí)際中一般情況關(guān)注的是算法的最壞運(yùn)行情況，所以數(shù)組中搜索數(shù)據(jù)時(shí)間復(fù)雜度為O(N)
2.3常見時(shí)間復(fù)雜度計(jì)算舉例
實(shí)例1
計(jì)算Func2的時(shí)間復(fù)雜度：
void Func2(int N)
{
int count = 0;
for (int k = 0; k < 2 * N; ++k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n", count);
}基本操作執(zhí)行了2*N + 10次，而通過推導(dǎo)大O階方法
用常數(shù)1取代加法常數(shù)，得到2*N + 1
只保留最高階項(xiàng)，得到2*N
將最高階項(xiàng)的系數(shù)變?yōu)?，得到N
所以最后的時(shí)間復(fù)雜度是O(N)
實(shí)例2：計(jì)算Func3的時(shí)間復(fù)雜度
void Func3(int N, int M)
{
int count = 0;
for (int k = 0; k < M; ++k)
{
++count;
}
for (int k = 0; k < N; ++k)
{
++count;
}
printf("%d\n", count);
}時(shí)間復(fù)雜度為O(N+M)
實(shí)例3：計(jì)算Func4的時(shí)間復(fù)雜度
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}用常數(shù)1替代100，時(shí)間復(fù)雜度是O(1)
實(shí)例4：計(jì)算strchr的時(shí)間復(fù)雜度
const char* strchr(const char* str, int character)
{
while (*str != character)
{
str++;
}
return str;
}最快執(zhí)行了1次，最慢執(zhí)行了N次，所以時(shí)間復(fù)雜度是O(N)
實(shí)例5：計(jì)算BubbleSort的時(shí)間復(fù)雜度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}第一趟冒泡排序了N - 1次，第二趟冒泡排序了N - 2次，依次類推，排序這個(gè)基本操作在最壞的情況下一共執(zhí)行了(N*(N+1)/2次，而最好的情況下是數(shù)組已經(jīng)排好了，此時(shí)只需要執(zhí)行N次，時(shí)間復(fù)雜度取最壞的情況，所以是O(N^2)
實(shí)例6：計(jì)算BinarySearch的時(shí)間復(fù)雜度
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號
while (begin <= end)
{
int mid = begin + ((end - begin) >> 1);
if (a[mid] < x)
begin = mid + 1;
else if (a[mid] > x)
end = mid - 1;
else
return mid;
}
return -1;
}假如有序數(shù)組有N個(gè)數(shù)，那么查找一次就會將數(shù)組的范圍縮小一半，直到最后只剩下一個(gè)數(shù)
可以這么用數(shù)字表示：
N / 2 / 2 / 2 / 2 / 2 / 2 ...... / 2 / 2 = 1
假設(shè)查找了x次，也就是每次將數(shù)組縮小一半(除以2)這個(gè)基本操作執(zhí)行了x次，那么這個(gè)x與N之間的關(guān)系是2^x = N
那么x = logN，這里默認(rèn)底數(shù)為2
所以時(shí)間復(fù)雜度是O(logN)
實(shí)例7：計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}基本操作遞歸了N次，所以時(shí)間復(fù)雜度為O(N)
實(shí)例8：計(jì)算斐波那契遞歸Fib的時(shí)間復(fù)雜度
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
基本操作遞歸了約為2^N次，根據(jù)推到大O階的方法，所以最后的時(shí)間復(fù)雜度為O(N)
3.空間復(fù)雜度
空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲空間大小的量度
空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用大O漸進(jìn)表示法。
注意：函數(shù)運(yùn)行時(shí)所需要的?？臻g(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請的額外空間來確定。
實(shí)例1：計(jì)算BubbleSort的空間復(fù)雜度
void BubbleSort(int* a, int n)
{
assert(a);
for (size_t end = n; end > 0; --end)
{
int exchange = 0;
for (size_t i = 1; i < end; ++i)
{
if (a[i - 1] > a[i])
{
Swap(&a[i - 1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}
可見，紅框標(biāo)注的地方，是在函數(shù)的內(nèi)部額外創(chuàng)建了4個(gè)變量，也就是開辟了常數(shù)個(gè)額外空間，所以空間復(fù)雜度為O(1)
實(shí)例2：計(jì)算Fibonacci的空間復(fù)雜度
// 返回斐波那契數(shù)列的前n項(xiàng)
long long* Fibonacci(size_t n)
{
if (n == 0)
return NULL;
long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n; ++i)
{
fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
}
return fibArray;
}在動(dòng)態(tài)內(nèi)存中開辟了N+1個(gè)sizeof(long long)大小的空間，所以空間復(fù)雜度為O(N)
實(shí)例3：計(jì)算階乘遞歸Fac的空間復(fù)雜度
long long Fac(size_t N)
{
if (N == 0)
return 1;
return Fac(N - 1) * N;
}遞歸調(diào)用了N次，開辟了N個(gè)棧幀，每個(gè)棧幀使用了常數(shù)個(gè)空間，所以空間復(fù)雜度為O(N)
實(shí)例4：計(jì)算Fibonacci的空間復(fù)雜度
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}每一次遞歸調(diào)用時(shí)，每兩個(gè)子函數(shù)用的函數(shù)棧幀空間都是同一個(gè)，所以只額外開辟了N個(gè)棧幀，空間復(fù)雜度為O(N)
4.常見復(fù)雜度對比
5.復(fù)雜度的OJ練習(xí)
5.1消失的數(shù)字OJ
鏈接：//img.jbzj.com/file_images/article/202207/202207081035315
題目描述：數(shù)組nums包含從0到n的所有整數(shù)，但其中缺了一個(gè)。請編寫代碼找出那個(gè)缺失的整數(shù)。你有辦法在O(n)時(shí)間內(nèi)完成嗎？
示例 1：
輸入：[3,0,1]
輸出：2
示例 2：
輸入：[9,6,4,2,3,5,7,0,1]
輸出：8
這里給出時(shí)間復(fù)雜度都為O(N)的思路
- 1.創(chuàng)建一個(gè)大小為N + 1的數(shù)組，然后用-1將數(shù)組初始化，再將題目中給定數(shù)組中的數(shù)字放到新創(chuàng)建數(shù)組中對應(yīng)下標(biāo)的位置，最后將新數(shù)組中的數(shù)字遍歷一遍，找出-1所對應(yīng)的下標(biāo)，該下標(biāo)的數(shù)字就是所要找的消失的數(shù)字了。
- 2.將題目給定數(shù)組中的數(shù)字全都異或一次，再與從0到N+1的數(shù)字全部異或一次，就可以得到那個(gè)消失的數(shù)字了，其思路類似于在一個(gè)數(shù)組中尋找單身狗。
- 3.將題目給定數(shù)組進(jìn)行快速排序，而后進(jìn)行二分查找，找不到的那個(gè)數(shù)字即為要找的數(shù)字了。
- 4.將N+1個(gè)數(shù)字進(jìn)行全都加起來，然后減去題目給定數(shù)組中的N個(gè)數(shù)字，最后得到的數(shù)字就是要找的消失的數(shù)字了。
3.2 旋轉(zhuǎn)數(shù)組OJ
鏈接：//img.jbzj.com/file_images/article/202207/202207081035316
題目描述：給你一個(gè)數(shù)組，將數(shù)組中的元素向右輪轉(zhuǎn) k 個(gè)位置，其中 k 是非負(fù)數(shù)。
示例 1:
輸入: nums = [1,2,3,4,5,6,7], k = 3
輸出: [5,6,7,1,2,3,4]
解釋:
向右輪轉(zhuǎn) 1 步: [7,1,2,3,4,5,6]
向右輪轉(zhuǎn) 2 步: [6,7,1,2,3,4,5]
向右輪轉(zhuǎn) 3 步: [5,6,7,1,2,3,4]
示例 2:
輸入：nums = [-1,-100,3,99], k = 2
輸出：[3,99,-1,-100]
解釋:
向右輪轉(zhuǎn) 1 步: [99,-1,-100,3]
向右輪轉(zhuǎn) 2 步: [3,99,-1,-100]
這里給出3種思路：
- 1.將最后一個(gè)數(shù)用一個(gè)臨時(shí)變量保存起來，然后將數(shù)組中前面的數(shù)依次往后挪動(dòng)，最后將臨時(shí)變量中的數(shù)放到數(shù)組的第一個(gè)位置，這樣的操作循環(huán)k次，最壞的情況下是k=N-1，這時(shí)時(shí)間復(fù)雜度是O(N^2)，而空間復(fù)雜度是O(1)，因?yàn)橹婚_辟了1個(gè)臨時(shí)變量，并且這個(gè)變量的空間是重復(fù)利用的。
- 2.額外開辟一個(gè)同樣大小的數(shù)組，然后按照k的大小截取數(shù)據(jù)依次放入數(shù)組中，這種做法的時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(N)，這是以空間來換時(shí)間的做法。
- 3.根據(jù)k的大小將數(shù)組分位2個(gè)部分，第1個(gè)部分和第2個(gè)部分分別自旋，最后再將整個(gè)數(shù)組自旋一次，由于旋轉(zhuǎn)交換的過程中只開辟了一個(gè)臨時(shí)變量的空間，所以空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(N)。
void reverse(int* nums, int left, int right)
{
while (left < right)
{
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
++left;
--right;
}
}
void rotate(int* nums, int numsSize, int k){
k %= numsSize;
reverse(nums, 0, numsSize - 1 - k);
reverse(nums, numsSize - k, numsSize - 1);
reverse(nums, 0, numsSize - 1);
}到此這篇關(guān)于C語言算法的時(shí)間復(fù)雜度和空間復(fù)雜度的文章就介紹到這了,更多相關(guān)C語言時(shí)間復(fù)雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C語言編程中的布爾bool數(shù)據(jù)類型,bool并不是需要通過C++才能使用的,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細(xì)介紹了C語言的結(jié)構(gòu)體，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C語言實(shí)現(xiàn)電器銷售管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)電器銷售管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
C語言中的函數(shù)指針基礎(chǔ)學(xué)習(xí)教程
這篇文章主要介紹了C語言中的函數(shù)指針基礎(chǔ)學(xué)習(xí)教程,包括函數(shù)指針作為參數(shù)來傳遞等重要知識,需要的朋友可以參考下2016-04-04
當(dāng)在Windows上使用C++進(jìn)行FTP上傳和下載時(shí),您可以使用libcurl庫來簡化操作,本文將為大家詳細(xì)介紹具體步驟,感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-12-12
方陣順時(shí)針旋轉(zhuǎn)的實(shí)現(xiàn)代碼
以下是關(guān)于方陣順時(shí)針旋轉(zhuǎn)的實(shí)現(xiàn)代碼。需要的朋友參考下2013-05-05
C語言數(shù)據(jù)類型與sizeof關(guān)鍵字
這篇文章主要介紹了C語言數(shù)據(jù)類型與sizeof關(guān)鍵字，C語言的數(shù)據(jù)類型包括基本類型、構(gòu)造類型、指針類型以及空類型，下文更多相關(guān)內(nèi)容需要的小伙伴可以參考一下2022-04-04
Qt使用SQLite數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)增刪改查
這篇文章主要為大家詳細(xì)介紹了Qt如何使用SQLite數(shù)據(jù)庫實(shí)現(xiàn)數(shù)據(jù)增刪改查功能，文中的示例代碼講解詳細(xì)，感興趣的小伙伴可以跟隨小編一起了解一下2023-06-06
淺析C語言中printf(),sprintf(),scanf(),sscanf()的用法和區(qū)別
以下是對C語言中printf(),sprintf(),scanf(),sscanf()的用法以及區(qū)別進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下2013-07-07
本文主要介紹了C++語言pow函數(shù)的具體使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03