# 時間複雜度(Time Complexity)

度量一個程序(演算法)執行時間的兩種方法：
1. **事後統計**
這種方法可行，但有兩個問題：
一：要想對設計的演算法的運行性能進行評測，需要實際運行該程式；
二：所得時間的統計量依賴於電腦的硬體、軟體等環境因素，這種方式，要在同一臺電腦的相同狀態下運行，才能比較那個演算法速度更快。
2. **事前估算**
通過分析某個演算法的時間複雜度來判斷哪個演算法更優。

## 時間頻度

一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多，而一個演算法中的**語句執行次數**稱為語句頻度或時間頻度，記為`T(n)`，即為定義為任何大小的輸入 n 所需的最大執行時間。

### 舉例說明

**第一種：**

public int fun1(int n){
    int total;
    for(int i = 0; i <= n; i++){
        total+=i;
    }
    return total;
}

其 `T(n) = n+1`，為什麼是 n+1 呢？
因為這個for循環需要n次，for循環本身也還需要判斷一次，所以是 `n+1`。
而這個 T(n) = n+1 代表的意義為：**不管 n 輸入多大，這個程式都至少需要做 n+1次。**

**第二種：**

public int fun2(int n){
    int total = (1 + n)*n/2;
    return total;
}

而這個方法其 T(n) = 1，因為不論 n 輸入多大數，它都只需要做 1 次。

### n 趨近無限大

當 n 趨向無限大時，有三個需要忽略的：

1. **忽略常數項**



**結論**
* 2n+20 和 2n 隨著n 變大，執行曲線無限接近，20可以忽略
* 3n+10 和 3n 隨著n 變大，執行曲線無限接近，10可以忽略

2. **忽略低次項**



**結論**
* 2n^2^+3n+10 和 2n^2^ 隨著n 變大，執行曲線無限接近，可以忽略 3n+10
* n^2^+5n+20 和 n^2^ 隨著n 變大，執行曲線無限接近，可以忽略 5n+20

3. **忽略係數**



**結論**
* 隨著n值變大，5n^2^+7n 和 3n^2^+2n，執行曲線重合，說明這種情況下5和3可以忽略。
* 而n^3^+5n 和 6n^3^+4n，執行曲線分離，說明多少次方是關鍵

## 時間複雜度
一般情況下，演算法中的基本操作語句的重複執行次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n)，使得當n趨近於無窮大時，`T(n) / f(n)` 的極限值為不等於零的常數，則稱`f(n)`是`T(n)`的同數量級函數。記作 `T(n)=Ｏ(f(n))`，稱Ｏ(f(n))  為演算法的漸進時間複雜度，簡稱時間複雜度。

我先說，如果有人能光靠上面這段文字就聽懂了 T(n) f(n) 和 O(n) 之間的關係，那我先下跪(不是

舉個例子好了：

假設 `T(n)=n+1`；`f(n)=n`

那麼 `T(n) / f(n) = 1`

剛剛前面有說過，T(n) / f(n) 的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數，所以這邊的 f(n)是T(n)的同數量級函數，記作 `T(n)=Ｏ(f(n))` 也就是 `T(n) = O(n)`

T(n)不同但時間複雜度可能相同，例如：
* T(n) = n^2^+7n+6
* T(n) = 3n^2^+2n+2

他們的T(n)不同，但時間複雜度相同，都為 `O(n²)`。

### 計算方法
* 用常數1代替運行時間中的所有加法常數  `T(n)=3n²+7n+6 => T(n)=3n²+7n+1`
* 修改後的運行次數函數中，只保留最高階項  `T(n)=3n²+7n+1 => T(n) = 3n²`
* 去除最高階項的系數 `T(n) = 3n² => T(n) = n² => O(n²)`

### 常見時間複雜度

* 常數階 O($1$)
* 對數階 O($log_2n$)
* 線性階 O($n$)
* 線性對數階 O($nlog_2n$)
* 平方階 O($n^2$)
* 立方階 O($n^3$)
* k次方階 O($n^k$)
* 指數階 O($2^n$)

常見的演算法時間複雜度由小到大依次為：
:::warning
Ο($1$)＜Ο($log_2n$)＜Ο($n$)＜Ο($nlog_2n$)＜Ο($n^2$)＜Ο($n^3$)＜ Ο($n^k$) ＜Ο($2^n$)
:::

隨著問題規模n的不斷增大，上述時間複雜度不斷增大，演算法的執行效率越低。

從圖中可見，我們應該盡可能避免使用**指數階**的演算法。

**1.常數階O($1$)**

無論程式碼執行了多少行，只要是沒有循環等複雜結構那麼這個程式碼的時間複雜度都是 O(1)，因為它消耗的時間並不會因為某個變數增長而增加，那麼無論這類程式碼有多長，都可以用 `O(1)` 來表示其時間複雜度。

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

**2.對數階O($log_2n$)**

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

在while循環裡面，每次都將 i 乘以 2，乘完之後 i 距離 n 就越來越近了。

假設循環 x 次之後 $i >= n$ ，此時這個循環便會退出，也就是說 $2^x >= n$，那麼 x = $log_2n$，當循環 $log_2n$ 次以後，這個代碼就會結束，因此時間複雜度為：O($log_2n$)。

$O(log_2n)$ 的這個 2 實際上是根據程式碼變化的，若將之改為 `i = i * 3` ，則是 O($log_3n$)。

**3.線性階O($n$)**

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

這段程式碼中 for循環裡的程式碼會執行 n 次，因此它消耗的時間是隨 n 的變化而變化，所以時間複雜度為 `O(n)`。

**線性對數階 O($nlogN$)**

for(i = 1; i < n; i++) {
	i = 1;
	while(i < n) {
		i = i * 2;
	}
}

將時間複雜度為 `O(logn)`的程式碼循環 N 遍即其時間複雜度就是 n*O(logn)，也就是 `O(nlogn)`。

**4.平方階O($n^2$)**

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

將時間複雜度為 O(n)的程式碼再嵌套循環 n 遍即其時間複雜度就是 O(n*n) = `O(n^2)`。

如果將其中一層的n改為m，其時間複雜度就變成了 `O(m*n)`。

**5.立方階 O($n^3$) 、K次方階 O($n^k$)**

參考上面的 O($n^2$)去理解就可以。

## 平均和最壞時間複雜度

時間複雜度還分為平均和最壞時間複雜度。

**平均時間複雜度**是指所有可能的輸入實例均以**等概率出現**的情況下，該演算法的運行時間。

最壞情況下的時間複雜度稱**最壞時間複雜度**，一般而言我們所討論的時間複雜度均是最壞情況下的時間複雜度。

這樣做的原因是：最壞情況下的時間複雜度是演算法在任何輸入實例上運行時間的界限，這就保證了演算法的運行時間不會比最壞情況更長。

平均時間複雜度和最壞時間複雜度是否一致，和演算法有關。

> *圖片來源：https://blog.csdn.net/jianyuerensheng/article/details/51263709*

由此圖可以得出：泡沫、簡單選擇、插入、堆、合併排序法的平均和最差時間複雜都是一致的，而且泡沫、簡單選擇、插入排序法的時間複雜度皆為 O($n^2$)，我們可以理解為這幾個排序法至少都需要雙層for循環才能夠搞定。

合併和堆排序法的平均和最差都是線性對數階，所以我們可以知道在**同等情況下**合併和堆排序法速度會比泡沫、簡單選擇、插入排序法來的快。

希爾排序法的平均時間是線性對數階，最差是介於線性階和平方階。

快速排序法在最差情況下是平方階，最快是線性對數階。

其它就自行瀏覽，先有個印象。

## 空間複雜度

類似於時間複雜度的討論，一個演算法的空間複雜度定義為該演算法所耗費的儲存空間，它也是問題規模 n 的函數。

空間複雜度是一個演算法在運行過程中臨時占用儲存空間大小的量度，有的演算法需要占用的臨時工作單元數與解決問題的規模 n 有關，它隨著 n 的增大而增加，當 n 較大時，將佔用較多的存儲單元，例如快速排序法、基數排序法和合併排序法就屬於這種情況。

但是在做演算法分析的時候我們主要還是以時間複雜度來衡量，因為對使用者來說他們只看重速度不在乎你的空間用了多少。一些緩存產品(Redis、Memcached)和演算法(基數排序法)本質就是用空間換時間。