時間復雜度(Time Complexity)

前言

時間復雜度應該是計算機專業中一個很重要的知識，重要到你有可能因為沒好好掌握而被面試官刷掉，正好現在大二正在學資料結構，寫這篇博客既是為了鞏固一下自己的掌握程度，同時也幫大家復習復習或是介紹一下，

概念介紹

為了用一種不受演算法所用語言以及編譯程式不同或機器性能影響的方法來評估演算法的效率，我們通常選取所研究問題的基本操作的執行次數作為整個演算法的時間量度，但在某些情況下，演算法的執行次數計算可能難以計算，因此引入時間復雜度作為演算法規模大小的衡量工具，是對演算法效率好壞的一種非定量表示，

時間復雜度：

一般情況下，演算法中基本操作的重復執行次數是問題規模n的某個函式f(n) ,演算法的時間量度記作： T ( n ) = O ( f ( n ) ) T(n)=O(f(n)) T(n)=O(f(n))
它表示隨著問題規模n的增大，演算法執行時間的增長率不超過f(n)的增長率，也就是所謂的時間復雜度

基本操作：

基本操作通常指演算法中最深層回圈的陳述句，它也是演算法最核心的陳述句，同時基本操作的重復執行次數與整個演算法的執行時間成正比，通常是對變數的賦值、數學運算等，一般通過演算法本身的目的來確定，比如，一個交換排序演算法，其基本操作就是最內層的交換賦值操作，只有在確定了演算法的基本操作后，才能計算演算法的時間復雜度，

頻度(Frequency Count)

指基本操作的重復執行次數，屬于定量計算

如何計算時間復雜度

第一步已經介紹過，下面著重講解中間兩個核心步驟

1.計算基本操作的頻度

拿幾個簡單的例子來說：

例1

int x=1;
++x;

那么很簡單，基本操作是x的自增，同時它僅僅執行了一次，即頻度為1，而且它的執行次數與x的賦值大小無關，也就是與問題規模n無關，因此f(n)=1，即T(n)=O(1)
例2

for(i=1;i<=n;++i){
	++x;
}

與例1相似，++x的執行次數為n次，即f(n)=n，隨著問題規模n的增大，所需時間越多，且與n的大小成正比
例3

for(i=1;i<=n;i++){
	for(int j=1;j<=n;j++){
		++x;
	}
}

例3也是同樣的道理，f(n)=n^2，不過是與二次方成正比

若遇到的是非常規問題，可以按以下方法處理（取自《資料結構》教材)：
1.對于并列回圈結構，取各回圈結構計算時間的最大值
2.對于嵌套回圈結構，取最內層回圈體中陳述句的執行次數
3.若各回圈之間無關系，采用乘法原則，將各回圈的次數相乘
4.對于遞回演算法，分解為兩部分計算：
(1)執行目前層次的遞回分解運算所需時間
(2)執行遞回呼叫所需時間

2.將頻度轉為時間復雜度

由于頻度是定量的精確計算，而時間復雜度是非定量的整體規模表示，因此要簡化舍去計算所得頻度，即“化簡”f(n)

簡化原則：

1.刪掉常數項以及常數系數
2.去掉低階項，保留最高階項

簡化舉例：

對于某演算法，
原 f ( n ) = 5 n 2 + 7 n + 9 原f(n)=5n^2+7n+9 原f(n)=5n2+7n+9
簡 化 后 F ( n ) = n 2 簡化后F(n)=n^2 簡化后F(n)=n2
因此該演算法時間復雜度為
T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)

符號O的解釋(也是從數學角度解釋為什么可以簡化)：
為了不含糊，這里解釋一下為什么是用符號O來表示時間復雜度，這里要特別宣告這個符號與高數中表示高階無窮小的小o()符號不是一個東西
百度百科對其定義如下：

簡單來說就是用一個更簡單的函式來描述一個項數較多的復雜函式的規模增長情況，形象一點說，我相信大家都去過小區售樓部吧，里面都會有一大塊的模型區域用來展示整個樓盤的布局，游泳池啊，車庫啊，活動中心啊這些，其實可以把這個理解為對小區規模的模擬和描述，這種模擬好處就是節約成本 （減少頻度計算量），可以忽略房子內部結構布局如下水管道，光纖等 (刪去低階項和常數因子，抓主略次)，更方便我們從整體的角度去分析，

當然你也可以以自己的方式理解，下面是我截取的百度對其的解釋：

最后給大家來個練習鞏固鞏固

現有如下代碼

int function(int n){
	int sum=0;
	for(int i=1;i<n+1;i++){
		for(int j=n;j>n-1;j--)
			for(int k=1;k<j+1;k++)
				sum++;
	}
	return sum;
}

請你求出sum++的頻度和函式function()的時間復雜度，歡迎大家踴躍評論，到時答案我會在評論中給出，