數據結構學習筆記-時間復雜度

張利勇發布于2019-08-16 13:43 / 1967人閱讀

摘要：原文地址數據結構學習筆記時間復雜度時間復雜度定義在進行算法分析時，語句總的執行次數是關于問題規模的函數，進而分析隨的變化情況并確定的數量級。同理，對于單純分支結構不包含在循環中的或語句而言，執行的次數都是恒定的，其時間復雜度也是。

原文地址：數據結構學習筆記-時間復雜度

時間復雜度定義

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

這樣用大寫O()來體現算法的時間復雜度的記法，我們稱之為大O記法。

推導大O階方法

如何分析一個算法的時間復雜度呢？即如何推導大O階呢？我們可以參考下面的推導方法。

推導大O階：
1. 用常數1取代運行時間中的所有加法常數。
2. 在修改后的運行次數函數中，只保留最高階項。
3. 如果最高階項存在且不是1，則去除與這個項相乘的常數。
得到的結果就是大O階。

下面讓我們根據這個推導方法來看幾個例子。

常數階

int sum = 0,n = 100;  /* 執行一次 */
sum = (1 + n) * n/2;  /* 執行一次 */
System.out.println(sum);  /* 執行一次 */

這段程序的執行次數是f(3)。我們使用大O階的方法推導一下：

將常數項3改為1。

保留最高階項。

沒有最高階項，所以這段程序的時間復雜度為O(1).

可以試想一下，如果這段代碼里的

sum = (1 + n) * n/2;  /* 執行一次 */

一共有10句，那么時間復雜度是多少呢？

事實上，無論有多少句該代碼，都不過是3次和多次的執行差異。像這種執行時間恒定的算法，我們稱之為具有O(1)的時間復雜度，又叫常數階。

注意：無論這個常數是多少，我們都記作O(1)。

同理，對于單純分支結構（不包含在循環中的if或switch語句）而言，執行的次數都是恒定的，其時間復雜度也是O(1)。

線性階

線性階的循環結構會復雜一些。要確定某個算法的階次，我們常常需要確定某個特定語句或某個語句集的運行次數。因此，我們要分析算法的復雜度，關鍵就是要分析循環結構的運行情況。

下面這段代碼，它的循環時間復雜度為O(n)，因為循環中的代碼須要執行n次。

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

對數階

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

由于每次count乘以2之后，就離n更近了一些。也就是是，有多少個2相乘后大于n，則會退出循環。由2^x=n得到x=log2n(以2為底n的對數)。所以這個循環的時間復雜度為O(logn)。

平方階

下面例子是一個循環嵌套，它的內循環時間復雜度為O(n)。

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

對于外循環不過是這個時間復雜度為O(n)的語句循環了n次，所以這段代碼的時間復雜度為O(n^2)。

如果外循環的次數改為了m，那么時間復雜度就變為了O(m*n)。

所以我們可以總結出來：循環的時間復雜度等于循環體的復雜度乘以循環運行的次數。

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

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

我們可以推導一下當i = 0 時，內循環執行了n次；當i = 1時，執行了n - 1次，……當 i = n-1時，執行了1次。所以總的執行次數為：

n + (n-1) + (n-2) + …… + 1 = n(n+1)/2 = n^2/2 + n/2

用推導大O階的方法

由于沒有加法常數，可以不考慮

只保留最高階，也就是保留n^2/2

去除常數的相乘項，也就是去除1/2

最終，這段代碼的時間復雜度就是O(n^2)。

常見的時間復雜度

該表列舉了一些常見的時間復雜度

執行次數函數	階	非正式術語
12	O(1)	常數階
2n+3	O(n)	線性階
3n^2+2n+1	O(n^2)	平方階
5log2n(2為底n的對數)+20	O(logn)	對數階
2n+3log2n(2為底n的對數)+19	O(nlgon)	nlogn階
6n^3+2n^2+3n+4	O(n^3)	立方階
2^n	O(2^n)	指數階

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

O(1)

云服務器 GPU云服務器數據結構時間復雜度時間復雜度快速排序時間復雜度最大流算法時間復雜度

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72207.html

算法學習筆記一、時空復雜度

摘要：動態規劃背包士兵路徑復雜度談算法一定要考慮復雜度時間復雜度和空間復雜度時間復雜度計算機基本操作的次數匯編指令的條數尋址跳轉空間復雜度所需占用的內存字節數兩者區別空間是可以返回利用的。面試求職班一筆記算法主要研究：時空復雜度算法的特征：有窮性，確定性，可行性，可能沒有輸入，但一定有輸出常用算法窮舉法（eg：求N個數的全排列；8皇后問題）減而治之（二分查找...

wuyumin 2019-08-16 11:08 評論0 收藏0
學習筆記 | HTML 基本結構和基本標簽 ——前端學習第一步！

摘要：基本結構語言中，一個頁面是由四個部分組成文檔聲明標簽對標簽對標簽對圖示文檔聲明這是一個文檔聲明，表示這是一個頁面。標簽標簽表示頁面內容的范圍。 HTML HTML ...

sPeng 2021-09-30 09:48 評論0 收藏0
「返現福利」極客時間返現二維碼匯總 + 學習筆記 + 知識腦圖

摘要：偶然復雜度的概念來源于軟件行業里有一本名著叫人月神話，書中提到兩個非常重要的概念本質復雜度和偶然復雜度。如何減少偶然復雜度引發的問題，讓軟件開發工作有序高效地進行，這正是作者希望通過程序員工作法這個專欄幫你解決的問題。極客時間專欄微信返現二維碼匯總有課學是一站式課程返現平臺，用戶通過掃描一下課程二維碼購買課程，提交購買截圖給有課學微信公眾號即可獲得返現。 showImg(https...

snowell 2019-07-01 12:48 評論0 收藏0