算法的時間復(fù)雜度和空間復(fù)雜度

一、時間復(fù)雜度：

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

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

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

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

到這里，我們先來談?wù)勅绾瓮茖?dǎo)大O階方法

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

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

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

得到的結(jié)果就是大O階

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

按照算法時間復(fù)雜的定義，我們?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的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。下面我們對其分析分析。

1.常數(shù)階

我們隨便給幾行代碼

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

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

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

2.線性階

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

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

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

3.對數(shù)階

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

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

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

4.平方階

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

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

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

所以我們可以總結(jié)得出，循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以該循環(huán)運(yùn)行的次數(shù)。那么下面這個循環(huán)嵌套，它的時間復(fù)雜度是多少呢？

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

由于當(dāng)i=0是，內(nèi)循環(huán)執(zhí)行了n次，當(dāng)i=1時，執(zhí)行了n-1次，.......當(dāng)i=n-1是，執(zhí)行了1次。所以總的執(zhí)行次數(shù)為n+（n-1）+（n-2）+....+1 = n（n+1）/2 = n*n/2+n/2；根據(jù)大O階推導(dǎo)的方法。最終這段代碼的時間復(fù)雜度為O（n*n）。

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

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

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ù)的時間復(fù)雜度是O（1）。所以整體的時間復(fù)雜度為O（n）

常用的時間復(fù)雜度所耗費(fèi)的時間從小到大依次是：

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

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

二、空間復(fù)雜度

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

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

看了這個標(biāo)準(zhǔn)官方的定義后，是不是有一點(diǎn)點(diǎn)小小的理解。

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

言外之意，我們這里不重點(diǎn)講解時間復(fù)雜度了。

通過以上的介紹，想必對時間復(fù)雜度與空間復(fù)雜度都了了自己的認(rèn)識了把，本次的博客也到此結(jié)束。

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

最新評論