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

一、時間復雜度：

首先，為什么會有這個概念的出現(xiàn)呢？

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

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

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

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

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

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

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

得到的結果就是大O階

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

按照算法時間復雜的定義，我們?nèi)×朔枪俜降拿Q，常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 線性對數(shù)階O(nlog2n),平方階O(n2)，立方階O(n3),...， k次方階O(nk),指數(shù)階O(2n)。隨著問題規(guī)模n的不斷增大，上述時間復雜度不斷增大，算法的執(zhí)行效率越低。下面我們對其分析分析。

1.常數(shù)階

我們隨便給幾行代碼

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

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

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

2.線性階

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

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

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

3.對數(shù)階

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

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

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

4.平方階

下面例子是一個循環(huán)嵌套，它的內(nèi)循環(huán)剛才我們已經(jīng)分析過。時間復雜度為O（n）

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

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

所以我們可以總結得出，循環(huán)的時間復雜度等于循環(huán)體的復雜度乘以該循環(huán)運行的次數(shù)。那么下面這個循環(huá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)循環(huán)執(zhí)行了n次，當i=1時，執(zhí)行了n-1次，.......當i=n-1是，執(zhí)行了1次。所以總的執(zhí)行次數(shù)為n+（n-1）+（n-2）+....+1 = n（n+1）/2 = n*n/2+n/2；根據(jù)大O階推導的方法。最終這段代碼的時間復雜度為O（n*n）。

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

對于方法調(diào)用的時間復雜度又如何分析。

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

上面這段代碼調(diào)用一個函數(shù)function（）

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

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

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

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

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

二、空間復雜度

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

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

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

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

言外之意，我們這里不重點講解時間復雜度了。

通過以上的介紹，想必對時間復雜度與空間復雜度都了了自己的認識了把，本次的博客也到此結束。

到此這篇關于C語言數(shù)據(jù)結構通關時間復雜度和空間復雜度的文章就介紹到這了,更多相關C語言時間與空間復雜度內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論