資訊專欄INFORMATION COLUMN
摘要：原文地址數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記時間復(fù)雜度時間復(fù)雜度定義在進行算法分析時，語句總的執(zhí)行次數(shù)是關(guān)于問題規(guī)模的函數(shù)，進而分析隨的變化情況并確定的數(shù)量級。同理，對于單純分支結(jié)構(gòu)不包含在循環(huán)中的或語句而言，執(zhí)行的次數(shù)都是恒定的，其時間復(fù)雜度也是。
原文地址：數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記-時間復(fù)雜度
時間復(fù)雜度定義在進行算法分析時，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級。算法的時間復(fù)雜度，也就是算法的時間量度，記作：T(n) = O(f(n))。它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度，簡稱為時間復(fù)雜度。其中f(n)是問題規(guī)模n的某個函數(shù)。
這樣用大寫O()來體現(xiàn)算法的時間復(fù)雜度的記法，我們稱之為大O記法。
推導(dǎo)大O階方法如何分析一個算法的時間復(fù)雜度呢？即如何推導(dǎo)大O階呢？我們可以參考下面的推導(dǎo)方法。
推導(dǎo)大O階： 1. 用常數(shù)1取代運行時間中的所有加法常數(shù)。 2. 在修改后的運行次數(shù)函數(shù)中，只保留最高階項。 3. 如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)。 得到的結(jié)果就是大O階。
下面讓我們根據(jù)這個推導(dǎo)方法來看幾個例子。
常數(shù)階int sum = 0,n = 100; /* 執(zhí)行一次 */ sum = (1 + n) * n/2; /* 執(zhí)行一次 */ System.out.println(sum); /* 執(zhí)行一次 */
這段程序的執(zhí)行次數(shù)是f(3)。我們使用大O階的方法推導(dǎo)一下：
將常數(shù)項3改為1。
保留最高階項。
沒有最高階項，所以這段程序的時間復(fù)雜度為O(1).
可以試想一下，如果這段代碼里的
sum = (1 + n) * n/2; /* 執(zhí)行一次 */
一共有10句，那么時間復(fù)雜度是多少呢？
事實上，無論有多少句該代碼，都不過是3次和多次的執(zhí)行差異。像這種執(zhí)行時間恒定的算法，我們稱之為具有O(1)的時間復(fù)雜度，又叫常數(shù)階。
注意：無論這個常數(shù)是多少，我們都記作O(1)。
同理，對于單純分支結(jié)構(gòu)（不包含在循環(huán)中的if或switch語句）而言，執(zhí)行的次數(shù)都是恒定的，其時間復(fù)雜度也是O(1)。
線性階線性階的循環(huán)結(jié)構(gòu)會復(fù)雜一些。要確定某個算法的階次，我們常常需要確定某個特定語句或某個語句集的運行次數(shù)。因此，我們要分析算法的復(fù)雜度，關(guān)鍵就是要分析循環(huán)結(jié)構(gòu)的運行情況。
下面這段代碼，它的循環(huán)時間復(fù)雜度為O(n)，因為循環(huán)中的代碼須要執(zhí)行n次。
for(int i = 0; i < n; i++){
}
對數(shù)階
int count = 1;
while(count < n){
count = count * 2;
}
由于每次count乘以2之后，就離n更近了一些。也就是是，有多少個2相乘后大于n，則會退出循環(huán)。由2^x=n得到x=log2n(以2為底n的對數(shù))。所以這個循環(huán)的時間復(fù)雜度為O(logn)。
平方階下面例子是一個循環(huán)嵌套，它的內(nèi)循環(huán)時間復(fù)雜度為O(n)。
int i,j;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
}
}
對于外循環(huán)不過是這個時間復(fù)雜度為O(n)的語句循環(huán)了n次，所以這段代碼的時間復(fù)雜度為O(n^2)。
如果外循環(huán)的次數(shù)改為了m，那么時間復(fù)雜度就變?yōu)榱薕(m*n)。
所以我們可以總結(jié)出來：循環(huán)的時間復(fù)雜度等于循環(huán)體的復(fù)雜度乘以循環(huán)運行的次數(shù)。
那么，下面這段代碼的時間復(fù)雜度是多少呢？
int i,j;
for(i = 0; i < n; i++){
for(j = i; j < n; j++){
}
}
我們可以推導(dǎo)一下當(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^2/2 + n/2
用推導(dǎo)大O階的方法
由于沒有加法常數(shù)，可以不考慮
只保留最高階，也就是保留n^2/2
去除常數(shù)的相乘項，也就是去除1/2
最終，這段代碼的時間復(fù)雜度就是O(n^2)。
常見的時間復(fù)雜度該表列舉了一些常見的時間復(fù)雜度
| 執(zhí)行次數(shù)函數(shù) | 階 | 非正式術(shù)語 |
|---|---|---|
| 12 | O(1) | 常數(shù)階 |
| 2n+3 | O(n) | 線性階 |
| 3n^2+2n+1 | O(n^2) | 平方階 |
| 5log2n(2為底n的對數(shù))+20 | O(logn) | 對數(shù)階 |
| 2n+3log2n(2為底n的對數(shù))+19 | O(nlgon) | nlogn階 |
| 6n^3+2n^2+3n+4 | O(n^3) | 立方階 |
| 2^n | O(2^n) | 指數(shù)階 |
常用的時間復(fù)雜度從小到大依次是：
O(1)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/72207.html
摘要：動態(tài)規(guī)劃背包士兵路徑復(fù)雜度談算法一定要考慮復(fù)雜度時間復(fù)雜度和空間復(fù)雜度時間復(fù)雜度計算機基本操作的次數(shù)匯編指令的條數(shù)尋址跳轉(zhuǎn)空間復(fù)雜度所需占用的內(nèi)存字節(jié)數(shù)兩者區(qū)別空間是可以返回利用的。 面試求職班一筆記 算法主要研究：時空復(fù)雜度 算法的特征： 有窮性， 確定性， 可行性， 可能沒有輸入，但一定有輸出 常用算法 窮舉法（eg：求N個數(shù)的全排列；8皇后問題） 減而治之（二分查找...
摘要：基本結(jié)構(gòu)語言中，一個頁面是由四個部分組成文檔聲明標(biāo)簽對標(biāo)簽對標(biāo)簽對圖示文檔聲明這是一個文檔聲明，表示這是一個頁面。標(biāo)簽標(biāo)簽表示頁面內(nèi)容的范圍。 HTML HTML ...
摘要：偶然復(fù)雜度的概念來源于軟件行業(yè)里有一本名著叫人月神話，書中提到兩個非常重要的概念本質(zhì)復(fù)雜度和偶然復(fù)雜度。如何減少偶然復(fù)雜度引發(fā)的問題，讓軟件開發(fā)工作有序高效地進行，這正是作者希望通過程序員工作法這個專欄幫你解決的問題。 極客時間專欄微信返現(xiàn)二維碼匯總 有課學(xué)是一站式課程返現(xiàn)平臺，用戶通過掃描一下課程二維碼購買課程，提交購買截圖給有課學(xué)微信公眾號即可獲得返現(xiàn)。 showImg(https...
閱讀 6979·2021-09-22 15:36
閱讀 5738·2021-09-02 10:20
閱讀 1886·2019-08-30 15:44
閱讀 2666·2019-08-29 14:06
閱讀 1165·2019-08-29 11:17
閱讀 1618·2019-08-26 14:05
閱讀 3115·2019-08-26 13:50
閱讀 1563·2019-08-26 10:26
