愛華網(wǎng)同一問題可用不同算法解決，而一個算法的質(zhì)量優(yōu)劣將影響到算法乃至程序的效率。算法分析的目的在于選擇合適算法和改進(jìn)算法。 計算機(jī)科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間。這是一個關(guān)于代表算法輸入值的字符串的長度的函數(shù)。時間復(fù)雜度常用大O符號表述，不包括這個函數(shù)的低階項和首項系數(shù)。使用這種方式時，時間復(fù)雜度可被稱為是漸近的，它考察當(dāng)輸入值大小趨近無窮時的情況。
時間復(fù)雜度_時間復(fù)雜度 -算法復(fù)雜度
算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。其作用： 時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量；而空間復(fù)雜度是指執(zhí)行這個算法所需要的內(nèi)存空間。（算法的復(fù)雜性體現(xiàn)在運行該算法時的計算機(jī)所需資源的多少上，計算機(jī)資源最重要的是時間和空間（即寄存器）資源，因此復(fù)雜度分為時間和空間復(fù)雜度）。
時間復(fù)雜度_時間復(fù)雜度 -基本介紹
算法復(fù)雜度分為時間復(fù)雜度和空間復(fù)雜度。其作用： 時間復(fù)雜度是度量算法執(zhí)行的時間長短；而空間復(fù)雜度是度量算法所需存儲空間的大小。
時間頻度
時間復(fù)雜度
一個算法執(zhí)行所耗費的時間，從理論上是不能算出來的，必須上機(jī)運行測試才能知道。但我們不可能也沒有必要對每個算法都上機(jī)測試，只需知道哪個算法花費的時間多，哪個算法花費的時間少就可以了。并且一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比例，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。一個算法中的語句執(zhí)行次數(shù)稱為語句頻度或時間頻度。記為T(n)。
計算方法
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
{
for(j=1;j
{
c[ i ][ j ]=0; //該步驟屬于基本操作 執(zhí)行次數(shù)：n的平方 次
for(k=1;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次方。
基本分類
按數(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ù)雜度 -空間復(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ù)雜度。
時間復(fù)雜度_時間復(fù)雜度 -漸近記號
1、Theta記號
2、大O記號
3、Omega記號
4、小o記號
時間復(fù)雜度_時間復(fù)雜度 -性質(zhì)
一個算法所耗費的時間=算法中每條語句的執(zhí)行時間之和
每條語句的執(zhí)行時間=語句的執(zhí)行次數(shù)(即頻度(FrequencyCount))×語句執(zhí)行一次所需時間
算法轉(zhuǎn)換為程序后，每條語句執(zhí)行一次所需的時間取決于機(jī)器的指令性能、速度以及編譯所產(chǎn)生的代碼質(zhì)量等難以確定的因素。
若要獨立于機(jī)器的軟、硬件系統(tǒng)來分析算法的時間耗費，則設(shè)每條語句執(zhí)行一次所需的時間均是單位時間，一個算法的時間耗費就是該算法中所有語句的頻度之和。
愛華網(wǎng)本文地址 » http://www.klfzs.com/a/8103350103/67776.html
