C語言數據結構時間復雜度及空間復雜度簡要分析
一、時間復雜度和空間復雜度是什麼?
1.1算法效率定義
算法效率分為兩種,一種是時間效率——時間復雜度,另一種是空間效率——空間復雜度
1.2時間復雜度概念
時間復雜度,簡言之就是你寫一個代碼,它解決一個問題上需要走多少步驟,需要花費多長時間。打個簡單的比方:現在給10個數,要求找到7在哪裡1,2,3,4,5,6,7,8,9,10。我們要求寫一個代碼,同學狗蛋寫瞭一個暴力查找,從第一個數依次往後遍歷,他的算法要找7次,同學狗剩寫瞭一個二分法查找,隻要找2次,這就是時間復雜度的比較
算法中的基本操作的執行次數,為算法的時間復雜度
1.3空間復雜度概念
空間復雜度,是對一個算法在運行過程中臨時占用存儲空間大小的量度。舉個栗子:我們現在要求寫一個代碼,狗蛋啪啪啪敲瞭一大堆變量,程序運行瞭,狗剩就用瞭很少的變量,程序也運行瞭。但是他們兩個在代碼運行中變量多少不同,占用的內存多少是不一樣的。空間復雜度,它計算的是變量的個數。
二、如何計算常見算法的時間復雜度和空間復雜度
我們在計算時間/空間復雜度時用的都是大O漸進表示法(是一種估算法)
2.1時間復雜度計算
我們以一個簡單的函數舉例
代碼如下:
void func1(int n) { int i = 0; int j = 0; int k = 0; int count = 0; for (i = 0;i < n;i++) { for (j = 0;j < n;j++) { count++; } } for (k = 0;k < 3 * n - 1;k++) { count++; } }
試問:該函數如果被調用,要運行多少次?
我們清楚的看出i進去有n次,共有n個i,第一個for結束要運行n^ 2次,第二個for要執行3n-1次,共執行n^ 2+3n-1次
那麼我們這裡的時間復雜度是否就是n^2+3n-1呢?答案是否的
我們前面說過,時間復雜度和空間復雜度用的都是大O漸進表示法,是一種估算法
我們取的值,是取對表達式中影響最大的那個
我們以n^ 2+3 * n-1這個式子進行舉例:設f(n)=n^2+3n-1
n=1,f(n)=1+3-1=3
n=10,f(n)=100+30-1=129
n=100,f(n)=10000+300-1=10299
n=1000,f(n)=1002999
…
很容易發現,對f(n)影響最大的是n^ 2,設g(n)=n^2
n=1,g(n)=1
n=10,g(n)=100
n=100,g(n)=10000
n=1000,g(n)=1000000
…
當n越大,g(n)就越接近f(n)
那麼這裡的時間復雜度大O漸進表達法寫法是這樣的:O(n^2)
2.2空間復雜度計算
在學習空間復雜度的求解之前,我們要知道,空間復雜度也是用大O漸進表達法進行求解,我們計算的不是所占空間大小,而是變量的個數。先來看一段代碼:
代碼如下(示例):
#include<stdio.h> 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; } }
在上面這個代碼中,我們創建瞭三個變量分別是size_t end
、int exchange
、size_t i
,盡管我們這個函數會經歷很多的循環,但這三個變量是反復使用的,也就是說他們所占的空間是被反復使用的,空間的多少是沒有變的,這裡區別時間復雜度——時間是累計的,空間是不累計的(對於時間復雜度,每次循環都會被計算;對於空間復雜度,空間是可以被反復使用的)。
我們上面說過,空間復雜度計算也是用的大O漸進表示法,對於常數,我們統一用O(1)表示(大O漸進表示法詳情見時間和空間復雜度篇1)
ps1:assert通常用於診斷程序中潛在的BUG,通過使用assert(condition), 當condition為false時,程序提前結束運行,利於程序BUG的定位。
ps2:size_t是一種類型,把它看作long unsigned int
我們再來看一段代碼:
代碼如下(示例):
//計算bubblesort的空間復雜度 #include<stdio.h> long long Factorial(size_t n) { return N < 2 ? N : Factorial(n - 1)*n; }
這段代碼是一個很簡單的遞歸實現階乘運算,那麼它的空間復雜度是多少呢?我們先假設傳過去的n=10。
10傳過來我們會進行10次遞歸,每次遞歸是創建一個函數棧幀(也就是一個空間),共創建10次,每一次的空間復雜度都是O(1)。把10換成n,也就是進行n次遞歸,每次遞歸會創建1個函數棧幀,空間復雜度是O(n)。
ps:可能會有小夥伴問,那函數棧幀遞歸往回走的時候不是銷毀瞭嗎?註意:這裡的空間復雜度是計算的“最壞、最多的情況”,況且不管是什麼函數,在使用過後其棧幀都會銷毀,空間復雜度算的是它用的空間最多的時候。
2.3快速推倒大O漸進表達法
1.常數1代替所有加法運算中的常數
2.隻保留最高階(高數極限思想)
3.若最高階存在且不為常數,則去除最高階的系數,比如3*n^ 9,去掉系數變為n^9
我們再來看兩個代碼訓練一下
代碼1如下:
void func2(int n) { int i = 0; int k = 0; int count = 0; for (i = 0;i < 3n;i++) { count++; } for (k = 0;k < 6;k++) { count++; } }
這裡f(n)=3n+6,它的大O漸進表達法就是O(n)
代碼2如下:
void func3(int n) { int i = 0; int count = 0; for (i = 0;i < 1000;i++) { count++; } }
這裡一眼就看出是運行1000次,用什麼來表示呢?前面說過:常數1代替所有加法運算中的常數,所以這裡不管常數有多大,隻要你隻有一個常數都用O(1)表示
一些註意事項:
O(1)這個時間復雜度的估值是不隨n的改變而改變的,以大白話說,不管你輸入的n是多少,我這個算法的效率是不變的
O(n)這個時間復雜度是隨n改變的
打個通俗的比方:設一個函數O(x)=1,那你x隨意多少,函數值都是1
設一個函數O(X)=x,那這裡函數值就隨x變換而變換瞭
三、一些特殊的情況
有些算法的時間復雜度是存在最好、平均、最壞情況:
最壞情況:任意輸入規模的最大運行次數(上界)
平均情況:任意輸入規模的期望運行次數
最好情況:任意輸入規模的最小運行次數(下界)
不多說,舉例說明:
代碼如下:
const char*strchr(char*str, char c) { while (*str != '\0') { if (*str == c) { return str; } ++str; } return NULL; }
上面的代碼是一個簡單的查找字符的函數,比如我們現在給一串字符共n個字符“aaaaba…aaac”(省略號省略a)
這裡查找a一下子就找到瞭,查找b要點功夫,查找c就更慢瞭,如果查找d,不好意思,查無此d。
那麼這裡就出現瞭最好情況:一次找到O(1)
平均情況:O(n/2)
最差情況:O(n)
對於這裡最壞情況可能有同學要說為什麼是O(n),你看最壞情況沒找到不是嗎?這裡解釋是這樣的,你找c要n次,找d是找不到也要找n次才能確定找不到。
總結
本文介紹瞭時間和空間復雜度的定義及大O漸進表達法的算法及一些特殊情況的解釋,希望對屏幕前的讀者有所幫助,祝您學習愉快!
更多關於數據結構時間復及空間復雜度的資料請關註WalkonNet其它相關文章!