? ? ?嗨嗨大家！本期帶來的內(nèi)容是：算法的時間復雜度與空間復雜度。

目錄

前言

一、算法效率

算法效率的衡量標準

二、時間復雜度

1 時間復雜度的定義

2 求解時間復雜度的步驟

2.1 找出算法中的基本語句：?

2.2計算基本語句執(zhí)行次數(shù)的數(shù)量級：

2.3大O階的漸進表示法：

3 代碼示例與解析

3.1 計算1+2+3+4+...+100的和

（1）常規(guī)算法

（2）高斯算法

3.2 求兩個n 階方陣C=A*B的乘積?

3.3 分析下面代碼的時間復雜度

（1）代碼1

（2）代碼2?

4 情況的判斷?

?三、空間復雜度

前言

? ?時間復雜度是衡量一個算法的好壞，也是算法題的重中之重。但是很多初學者認為時間復雜度不好理解，對于其復雜程序的估算無從下手。那么本篇文章將從簡單到復雜來介紹時間復雜度的計算方法，希望給迷茫的你們指明一條前進的方向。

一、算法效率

算法效率的衡量標準

? ?當給定一個算法時，我們要做兩項分析。第一項是以數(shù)學的角度來證明算法的正確性，這一步主要用到形式化證明的方法及相關的推理模式，例如數(shù)學歸納法。然而在證明算法正確的基礎上，便需要第二項的內(nèi)容了。第二項就要分析算法的時間復雜度與空間復雜度，算法在編寫成可執(zhí)行程序后，運行時需要耗費時間資源和空間（內(nèi)存）資源。因此衡量一個算法的好壞，一般是從時間和空間兩個維度來衡量的，即時間復雜度和空間復雜度。

二、時間復雜度

1 時間復雜度的定義

? ?在計算機科學中，算法的時間復雜度是一個函數(shù)。一個算法執(zhí)行所耗費的時間，從理論上說，是不能被算出來的，只有你把你的程序放在機器上跑起來，才能知道。但是若每個算法都需要上機測試，會很麻煩，所以才有了時間復雜度的分析方式。

? ?一個算法中的語句執(zhí)行次數(shù)稱為語句（時間）頻度，記作T(n)?，這里的n是問題的規(guī)模。當n不斷變化時，時間頻度T(n) 也會不斷變化。那我們就會想：它變化時呈現(xiàn)的規(guī)律是怎樣的？為此，來引入時間復雜度的概念。

? ?時間（計算）復雜度又稱時間復雜性，它是一個算法運行時間的相對度量。一個算法的運行時間長短，大致等于執(zhí)行簡單操作（賦值、比較、計算、轉(zhuǎn)向、返回、輸入和輸出）所需要的時間與算法中進行簡單操作次數(shù)的乘積。

2 求解時間復雜度的步驟

2.1 找出算法中的基本語句：?

? ?一般來說，算法中執(zhí)行次數(shù)最多的那條語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。

2.2計算基本語句執(zhí)行次數(shù)的數(shù)量級：

? ?這里僅計算基本語句執(zhí)行次數(shù)的數(shù)量級，意味著只要保留基本語句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，從而可以忽略所有低次冪和最高次冪的系數(shù)，進而能夠簡化算法分析。通常情況下，算法的基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n 的某個函數(shù)，用T(n) 表示

2.3大O階的漸進表示法：

? ?大O：用來描述函數(shù)漸進行為的數(shù)學符號。

? ?如果有某個輔助函數(shù)f(n) ，使得在n趨近于無窮大時，T(n) /f(n) 的極限值不等于0 的常數(shù)，則稱f(n) 是T(n) 的同數(shù)量級函數(shù)。記作T(n)=O(f(n))。

其實，簡單來說，就是保留求出次數(shù)的最高次冪，并把系數(shù)去掉。如：T(n)=2n^2+n+1=O(n^2)。

為方便大家理解，用代碼舉例：

#include<stdio.h> 	  
int main()  
{  
   int i, j, x = 0, sum = 0, n = 100;  //執(zhí)行1次//  
    for( i = 1; i <= n; i++)           //執(zhí)行n+1次//  
	 {  
	   sum = sum + i;                  // 執(zhí)行n次 //     
           for( j = 1; j <= n; j++)    // 執(zhí)行n*(n+1)次//  
	       {  
	          x++;                     //執(zhí)行n*n次//  
            	  sum = sum + x;       //執(zhí)行n*n次//  
              }  
	 }  
	    printf("%d", sum);             //執(zhí)行1次//  
}  

注：因為for語句會加到n+1，會執(zhí)行n+1次，而它的函數(shù)體在 i==n+1 時不滿足判斷條件，所以只執(zhí)行n次。

結(jié)論：要看清題目中問的是for語句的執(zhí)行次數(shù)，還是它的循環(huán)體執(zhí)行的次數(shù)。?

下面我們根據(jù)以上的代碼，來詳細推導“大O階”?的步驟。

• 第一步：用常數(shù) 1 取代運行時間中的所有加法常數(shù)。

則上面的算式變?yōu)椋簣?zhí)行總次數(shù) =3n^2 + 3n + 1，（直接相加的話，應該是T(n) = 1 + n+1 + n +n*(n+1) + n*n + n*n + 1 = 3n^2 + 3n + 3?，F(xiàn)在用常數(shù) 1 取代運行時間中的所有加法常數(shù)，就是把T(n) =3n^2 + 3n + 3中的最后一個3改為1. 就得到了 T(n) = 3n^2 + 3n + 1）

• 第二步：在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

這里的最高階是 n 的二次方，所以算式變?yōu)椋簣?zhí)行總次數(shù) = 3n^2

• 第三步：如果最高階項存在且不是 1 ，則去除與這個項相乘的常數(shù)。

這里 n 的二次方不是 1 所以要去除這個項的相乘常數(shù)，算式變?yōu)椋簣?zhí)行總次數(shù) = n^2，因此最后我們得到上面那段代碼的算法時間復雜度表示為： O( n^2 )。

下面把常見的算法時間復雜度以及它們在效率上的高低順序記錄在這里，使大家對算法的效率有個直觀的認識。?

O(1) 常數(shù)階<?O(logn) 對數(shù)階< O(n) 線性階 < O(nlogn) < O(n^2) 平方階 < O(n^3) < { O(2^n) < O(n!)< O(n^n) }

注：最后用大括號的三項即便是在n 的規(guī)模很小的情況下依然要耗費大量的時間，算法的時間復雜度大到無法想象，基本上是不可用的狀態(tài)。

看到這里，時間復雜度的相關原理就介紹完了。我們通過幾個代碼示例來具體分析時間復雜度的計算過程：

3 代碼示例與解析

3.1 計算1+2+3+4+...+100的和

（1）常規(guī)算法

#include<stdio.h>
int main()  
{  
    int i, sum = 0, n = 100;    //執(zhí)行1次//  
    for( i = 1; i <= n; i++)    //執(zhí)行n+1次//  
    {  
        sum = sum + i;          //執(zhí)行n次//  
        //printf("%d\n", sum);  
    }  
    printf("%d", sum);          //執(zhí)行1次//  
} 

?從附加的注釋可以看到各個代碼分別執(zhí)行了多少次。那么這寫代碼語句執(zhí)行次數(shù)的總和就可以理解為是該算法計算出結(jié)果所需要的時間。

該算法所用的時間（算法語句執(zhí)行的總次數(shù)）為： 1 + ( n + 1 ) + n + 1 = 2n + 3。

而當 n 不斷增大，比如我們這次所要計算的不是 1 + 2 + 3 + 4 +...?+ 100 = ？ 而是 1 + 2 + 3 + 4 + ...?+ n = ？其中 n 是一個十分大的數(shù)字，那么上述算法的執(zhí)行總次數(shù)（所需時間）會隨著 n 的增大而增加，但是在 for 循環(huán)以外的語句并不受n 的規(guī)模影響（永遠都只執(zhí)行一次）。所以我們可以將上述算法的執(zhí)行總次數(shù)簡單的記做： 2n ；又因為系數(shù)2可以忽略不記，則最終的結(jié)果即為n。

這樣我們就得到了我們設計的算法的時間復雜度，我們把它記作： O(n)。

（2）高斯算法

#include<stdio.h> 	  
int main()  
{  
	int sum = 0, n = 100;   //執(zhí)行1次//  
	sum = (1 + n) * n/2;    //執(zhí)行1次//  
	printf("%d", sum);      //執(zhí)行1次//  
}  

我們學到這里不難看出這個算法的時間復雜度： O(3)，但一般記作 O(1)。

結(jié)論：從算法的效率上看，O(1) <?O(n) ，所以高斯的算法更快，效率更高。?

3.2 求兩個n 階方陣C=A*B的乘積?

void MaMu(int A[n][n]，int B [n][n]，int C[n][n])
{  	  
	for(int i=0; i <n; i++)                           //n+1  
	{  
		for (j=0;j < n; j++)                          //n*(n+1)  
		{     
  			C[i][j]=0;                                //n^2  
			for (k=0; k<n; k++)                       //n^2*(n+1)  
			{  
           			 C[i][j]=C[i][j]+A[i][k]*B[k][j]; //n^3  
			}  
		}  
	}  
} 

?該算法所有語句的頻度之和為:T(n) = 2n^3+3n^2+2n+1;

?利用大O表示法，該算法的時間復雜度為O(n^3)。

3.3 分析下面代碼的時間復雜度

（1）代碼1

int i,j, n = 100;		
for(i = 0; i < n; i++)
{
	for(j = i; j < n; j++) //j = i而不是0//
    {
		  //時間復雜度為O(1)的程序步驟序列//

	}
}

在該程序中，當 i= 0時，內(nèi)循環(huán)執(zhí)行了n次，當 i =1時，執(zhí)行了n-1次，……當i =n-1時，執(zhí)行了1次。所以總的執(zhí)行次數(shù)為：n+(n-1)+(n-2)+…+ 1= n(n+1)/2= O(n^2)。

（2）代碼2?

void test(int arr[]， int n)  
{  
	int i, j, k;  
	for (i=0; i<n-1; i++)  
	{  
		k = i;  
		for (j=i+1; j<n; j++)  
		{  
			if (arr[k] > arr[j])  
			{  
 			    k = j;  
			}  
		}  
  		x = arr[i];  
	    arr[i] = arr[k];  
	    arr[k] = x;  
	}  
}  

其中，算法的基本語句是：

if(arr[k]>arr[j]
{
    k=j;
}

這里便可以知道，時間復雜度為O(1)。?執(zhí)行次數(shù)為：n-1 + n-2 + ... + n*(n-1)/2 = O(n^2)。

4 情況的判斷?

有些算法的時間復雜度存在最好、平均和最壞情況：（時間復雜度取最壞情況）

• ?最壞情況：任意輸入規(guī)模的最大運行次數(shù)(上界)
• ?平均情況：任意輸入規(guī)模的期望運行次數(shù)
• ?最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)

在實際中一般情況關注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復雜度為O(N）

• 最好情況：1次找到
• 最壞情況：N次找到
• 平均情況：N/2次找到

例：我們就下面代碼進行分析

//計算strchr的時間復雜度
int main()
{
   const char* strchr(const char* str,int character);
   return 0;
}

我們根據(jù)該函數(shù)原理進行分析：?

strchr函數(shù)的作用是在一個字符串中找到目標字符在該字符串中第一次出現(xiàn)的位置，并返回該位置；

最好情況：1次找到（目標字符就在字符串的第一個元素）；

最壞情況：N次找到（目標字符在字符串的末尾）；

平均情況：N/2次找到。

因此strchr 的時間復雜度為O(N) 。

?三、空間復雜度

? ?類似于時間復雜度的討論，一個算法的空間復雜度S(n) 定義為該算法所耗費的存儲空間，它也是問題規(guī)模n 的函數(shù)。漸近空間復雜度也常常簡稱為空間復雜度。算法空間復雜度的計算公式記作：S(n)=O(f(n))，其中，n 為問題的規(guī)模，f(n) 為語句關于n 所占存儲空間的函數(shù)。

? ?空間復雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度。一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入輸出數(shù)據(jù)所占用的存儲空間和算法在運行過程中臨時占用的存儲空間這三個方面。算法的輸入輸出數(shù)據(jù)所占用的存儲空間是由要解決的問題決定的，是通過參數(shù)表由調(diào)用函數(shù)傳遞而來的，它不隨本算法的不同而改變。存儲算法本身所占用的存儲空間與算法書寫的長短成正比，要壓縮這方面的存儲空間，就必須編寫出較短的算法。

如當一個算法的空間復雜度為一個常量，即不隨被處理數(shù)據(jù)量n 的大小而改變時，可表示為O(1)；當一個算法的空間復雜度與以2為底的n 的對數(shù)成正比時，可表示為O(log2n)；當一個算法的空間復雜度與n 成線性比例關系時，可表示為O(n)。

? ?通常， 我們都使用“時間復雜度”來指運行時間的需求，使用“空間復雜度”指空間需求。當不用限定詞地使用“復雜度”時，通常都是指時間復雜度。

? ? 本期分享已經(jīng)接近尾聲，那么大家對“復雜度”是否有了新的認識呢？如果這篇文章對你有所幫助，記得給博主一個三連哈~你們的支持是我創(chuàng)作的最大動力！前路漫漫，勿焦灼，勿煩躁。我們要有堅如磐石的信仰，腳下才有行穩(wěn)致遠的力量！諸君加油，不負自己！

文章來源地址http://www.zghlxwxcb.cn/news/detail-845611.html

到了這里，關于數(shù)據(jù)結(jié)構(gòu)學習之路--算法的時間復雜度與空間復雜度（精講）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！