C語言時間復雜度和空間復雜度實例分析

今天小編給大家分享一下C語言時間復雜度和空間復雜度實例分析的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

1.時間復雜度：

首先，為什么會有這個概念的出現呢？

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

這樣用大寫O（）來體現算法時間復雜度的記法，稱為大O記法。

你可以簡單這樣認為：算法時間復雜度實際上就是基本操作的執行次數。

到這里，我們先來談談如何推導大O階方法

（1）用常數1取代運行時間中的所有加法常數

（2）在修改后的運行次數函數中，只保留最高階項

（3）如果最高階項存在且其系數不是1，則去除與這個項相乘的系數。

得到的結果就是大O階

這仿佛就像是游戲攻略一樣，我們得到了一個推導算法時間復雜度的萬能公式。可是實際上，分析一個算法的時間復雜度，沒有這么的簡單。

按照算法時間復雜的定義，我們取了非官方的名稱，常數階O(1),對數階O(log2n),線性階O(n), 線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低。下面我們對其分析分析。

1.常數階

我們隨便給幾行代碼

int sum = 0,n = 100；
sum = (1+n)*n/2；
printf("%d",sum)；

大聲回答這個算法時間復雜度是O（3）還是O（1），答案肯定是O（1）啊，首先這個算法執行次數函數是f（n） = 3；根據我們推導大O階的方法，把3改為1，這是常數項，沒有其他項可，所以是O（1）。實際上無論n是多少，這種與問題的大小無關，執行時間恒定的算法，我們稱為具有O（1）的時間復雜度，又叫常數階。

注意：不管這個常數是多少，我們都記作O（1），而不是O（3），O（5）等其他數字，這是初學者常犯的錯誤。

2.線性階

線性階的循環結構會復雜很多。要確定某個算法的階次，我們需要確定某個特定語句運行的次數。

下面這段代碼，它的循環的時間復雜度為O（n），因為循環體中的代碼需要執行n次

int i;
for(i=0;i<n;i++)
{
/*時間復雜度為O（1）的程序步驟序列*/
}

3.對數階

下面這段代碼，時間復雜度又是多少呢？

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

由于每次count乘以2以后，就距離n更近了一分，也就是說，有多少個2相乘后大于n，則會退循環。有2的x次方＝n，x = log2n。所以這個循環的時間復雜度為O（longn）

4.平方階

下面例子是一個循環嵌套，它的內循環剛才我們已經分析過。時間復雜度為O（n）

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

而對于外層的循環，不過是內部這個時間復雜度為O（n）的語句，在循環n次。所以時間復雜度為O（n*n）；如果外層循環次數改為了m，那時間復雜度就為O（m*n）

所以我們可以總結得出，循環的時間復雜度等于循環體的復雜度乘以該循環運行的次數。那么下面這個循環嵌套，它的時間復雜度是多少呢？

int i,j;
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)/*注意j=i而不是o*/
{
/*時間復雜度為O（1）的程序步驟序列*/
}
}

由于當i=0是，內循環執行了n次，當i=1時，執行了n-1次，.......當i=n-1是，執行了1次。所以總的執行次數為n+（n-1）+（n-2）+....+1 = n（n+1）/2 = n*n/2+n/2；根據大O階推導的方法。最終這段代碼的時間復雜度為O（n*n）。

從這個例子我們可以知道，理解大O階推導不算難，難的是對數列的一些相關運算，這更多的是考察你的數學知識和能力，我們繼續看例子。

對于方法調用的時間復雜度又如何分析。

int i，j;
for(i = 0;i<n;i++)
{
function(i);
}

上面這段代碼調用一個函數function（）

void function(int count)
{
print(count);
}

函數體是打印count這個參數。這很好理解。function（）函數的時間復雜度是O（1）。所以整體的時間復雜度為O（n）

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

Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜…＜Ο(2n)＜Ο(n!)

實際上，對于算法的分析，一種方法時候計算所有情況的平均值，這中時間復雜度的計算方法稱為平均時間復雜度。另一種方法是計算最壞情況下的時間復雜度，這種方法稱為最壞時間復雜度。一般在沒有特殊說明的情況下，都是指最壞時間復雜度。

2.算法空間復雜度

類似于時間復雜度的討論，一個算法的空間復雜度(Space Complexity)S(n)定義為該算法所耗費的存儲空間，它也是問題規模n的函數。漸近空間復雜度也常常簡稱為空間復雜度。

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數據所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數據所占用的存儲空間是由要解決的問題決定的，是通過參數表由調用函數傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。算法在運行過程中臨時占用的存儲空間隨算法的不同而異，有的算法只需要占用少量的臨時工作單元，而且不隨問題規模的大小而改變，我們稱這種算法是“就地\"進行的，是節省存儲的算法，如這一節介紹過的幾個算法都是如此；有的算法需要占用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元。

看了這個標準官方的定義后，是不是有一點點小小的理解。

我們在寫代碼時，完全可以用空間來換取時間，比如判斷某某年是不是閏年這個問題的解決。就可以存儲空間來換取計算時間的小技巧。通常我們都使用“時間復雜度”來指運行時間的需求，使用“空間復雜度”指空間需求。當不用限定詞地使用“復雜度”時，通常都是指空間復雜度。

以上就是“C語言時間復雜度和空間復雜度實例分析”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。