zhb8015

編輯本段算法復(fù)雜度

　　算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。其作用： 時間復(fù)雜度是度量算法執(zhí)行的時間長短；而空間復(fù)雜度是度量算法所需存儲空間的大小。

編輯本段時間復(fù)雜度

1.時間頻度

　　一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個算法都上機測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。

2.計算方法

　　1. 一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個函數(shù)f（n），因此，算法的時間復(fù)雜度記做：T（n）=O（f（n）） 　　分析：隨著模塊n的增大，算法執(zhí)行的時間的增長率和f（n）的增長率成正比，所以f（n）越小，算法的時間復(fù)雜度越低，算法的效率越高。 　　2. 在計算時間復(fù)雜度的時候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)，再找出T（n）的同數(shù)量級（它的同數(shù)量級有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=該數(shù)量級，若T(n)/f(n)求極限可得到一常數(shù)c，則時間復(fù)雜度 T（n）=O（f（n）） 　　例：算法： 　　for（i=1;i<=n;++i） 　　{ 　　for(j=1;j<=n;++j) 　　{ 　　c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數(shù)：n的平方 次 　　for(k=1;k<=n;++k) 　　c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 執(zhí)行次數(shù)：n的三次方 次 　　} 　　} 　　則有 T（n）= n的平方+n的三次方，根據(jù)上面括號里的同數(shù)量級，我們可以確定 n的三次方 為T（n）的同數(shù)量級 　　則有f（n）= n的三次方，然后根據(jù)T（n）/f（n）求極限可得到常數(shù)c 　　則該算法的 時間復(fù)雜度：T（n）=O（n^3） 注：n^3即是n的3次方。

3.分類

　　按數(shù)量級遞增排列，常見的時間復(fù)雜度有： 　　常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n), 　　線性對數(shù)階O(nlog2n),平方階O(n^2)，立方階O(n^3),...， 　　k次方階O(n^k), 指數(shù)階O(2n) 。隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。

編輯本段空間復(fù)雜度

　 　一個程序的空間復(fù)雜度是指運行完一個程序所需內(nèi)存的大小。利用程序的空間復(fù)雜度，可以對程序的運行所需要的內(nèi)存多少有個預(yù)先估計。一個程序執(zhí)行時除了需 要存儲空間和存儲本身所使用的指令、常數(shù)、變量和輸入數(shù)據(jù)外，還需要一些對數(shù)據(jù)進(jìn)行操作的工作單元和存儲一些為現(xiàn)實計算所需信息的輔助空間。程序執(zhí)行時所 需存儲空間包括以下兩部分。 　　（1）固定部分。這部分空間的大小與輸入/輸出的數(shù)據(jù)的個數(shù)多少、數(shù)值無關(guān)。主要包括指令空間（即代碼空間）、數(shù)據(jù)空間（常量、簡單變量）等所占的空間。這部分屬于靜態(tài)空間。 　　（2）可變空間，這部分空間的主要包括動態(tài)分配的空間，以及遞歸棧所需的空間等。這部分的空間大小與算法有關(guān)。 　　一個算法所需的存儲空間用f(n)表示。 　　S(n)=O(f(n)) 　　其中n為問題的規(guī)模，S(n)表示空間復(fù)雜度。