---
# System prepended metadata

title: time complexity 時間複雜度
tags: [程設班講義]

---

# 簡介
是一種方便計算程式執行時間的方法，寫題目時算好時間複雜度並只適合的做法可以減少 $TLE$ 的機率。

符號為 $O(~~)$ ，通常以 $n$ 當作變數。

# 時間頻度
哪個演算法中語句執行次數多，他花費時間就多，而一個演算法中的語句執行次數稱為時間頻度，記為 $T(n)$ ，即為定義為任何大小的輸入 $n$ 所需的最大執行時間。

若 $T(n)=O(n^2)$，則代表 $T(n)$ 最差執行時間不超過 $O(n^2)$。

# 計算
在講之前要先說，當 $n$ 趨向無限大時，有三個需要忽略的：

## 忽略常數項

![](https://i.imgur.com/hGd3Sca.png)


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

## 忽略低次項

![](https://i.imgur.com/HN51vFP.png)


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

## 忽略係數

![](https://i.imgur.com/s5bhDPa.png)


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

## 總結
先找出最高次項再捨棄常數。

:::info
:::spoiler 範例
計算出執行次數 : $5n^2+8n+2$，則時間複雜度為最高次 $5n^2$ ，捨棄常數後為 $n^2$ ，則時間複雜度 $O(n^2)$。
:::

## 常見時間複雜度
![](https://i.imgur.com/z1EGYKQ.png)

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

$O(1)~ ＜~ Ο(logn)~＜~ Ο(n)~＜~Ο(nlogn)~＜~Ο(n^2)~＜~Ο(n^3)~＜~ Ο(n^k)~＜~Ο(2^n)$

## 舉例
$1.$
```cpp=
int n ;
if(n % 2 == 1) {
    cout << "奇數" ;
}
else{
    cout << "偶數" ;
}
```

:::spoiler 答案
執行次數都固定，時間複雜度為 $O(1)$。
:::

$2.$
```cpp=
int n ;
int arr[100] , k ;
int L = 0 , R = n , m ;
while(L <= R) {
    m = (L + R) / 2 ; 
    if(arr[m] == k) {
        break ;
    }
    else if(arr[n] < k) {
        L = m + 1 ;
    }
    else{
        R = m - 1 ;
    }
}
```

:::spoiler 答案
二分搜，每次將搜尋範圍減少一半，時間複雜度為 $O(\log n)$。
:::

$3.$
```cpp=
int arr[100], k ;
for(int i = 0 ; i < 100 ; i++) {
    if(arr[i] == k) {
        break ;
    }
}
```
:::spoiler 答案
在最差狀況中，$i$ 從 $0\sim n$，時間複雜度為 $O(n)$。
:::

$4.$
```cpp=
int n;
bool prime = true ;
for(int i = 2  i <= sqrt(n) ; i++) {
    if(n % i == 0) {
        prime = false ;
    }
}
```
:::spoiler 答案
判斷 $n$ 是否為質數，因為只需確定 $2\sim \sqrt{n}$ 中是否有 $n$ 的因數，所以時間複雜度為 $O(\sqrt{n})$。
:::

$5.$
```cpp=
int arr[100] ;
sort(arr , arr + 100) ;
```
:::spoiler 答案
內建 $sort$ ，時間複雜度為 $O(n \log n)$。
:::

$6.$
```cpp=
int n ;
int arr[100] = {} ;
for(int i = n - 1 ; i > 0 ; i--) {
    cin >> arr[i] ;
    sort(arr , arr+n) ;
}
```
:::spoiler `答案`
內建 $sort$ 為 $O(n \log n)$，共 $sort\ n$ 次，時間複雜度為 $O(n^2 \log n)$。
:::

$7.$
```cpp=
int arr[100] ;
for(int i = 0 ; i < 100 ; i++) {
    for(int j = 0 ; j < 100 - i - 1 ; j++) {
        if(arr[j] > arr[j + 1]) {
            swap(arr[j] , arr[j+1]) ;
        }
    }
}
```
:::spoiler 答案
$bubble\ sort$，執行時間從 $n-1$ 開始每次遞減 $1$ ，因此執行次數為 $(n-1)+(n-2)+(n-3)+\dots +1=\displaystyle\frac{n(n-1)}{2}$ ，時間複雜度為 $O(n^2)$。
:::

$8.$
```cpp=
int n ;
int arr[100] ;
sort(arr , arr + 100) ;
for(int i = 0 ; i < n ; i++) {
    for(int j = 0 ; j < n - i - 1; j++) {
        if(arr[j] < arr[j + 1]) {
            swap(arr[j] , arr[j + 1]) ;
        }
    }
}
```
:::spoiler `答案`
內建 $sort$ 為 $O(n \log n)$，之後再 $bubble\ sort$ 為 $O(n^2)$，取高次因此答案為$O(n^2)$。
:::


$9.$
```cpp=
int n , m , ans = 1 ;
cin >> n >> m ;
while(n) {
    if(n % 2 == 0){
        ans *= m ;
    }
    m *= m ;
    n /= 2 ;
}
```
:::spoiler `答案`
經典快速冪，計算 $m^n$，$n$ 每次 $\div ~2$ ，時間複雜度為 $O(\log n)$。
:::


$10.$
```cpp=
int n ;
for(int i = 0 ; i < n ; i++) {
    for(int j = 0 ; j < n ; j++) {
        for(int z = 0 ; z < n ; z++) {
            cout << '*' ;
        }
        cout << endl ;
    }
    cout << endl ;
}
```
:::spoiler 答案
輸出 $3$ 個 $n\times n$ 的正方形，$3$ 層迴圈皆執行 $n$ 次，時間複雜度為 $O(n^3)$。
:::

$11.$
```cpp=
int function(int n) {
    if(n == 0 || n == 1) {
        return 1 ;
    }
    return n * function(n - 1) ;
}
```
:::spoiler 答案
遞迴計算 $n!$，時間複雜度為 $O(n)$。
:::

$12.$
```cpp=
int n ;
int arr[100] ;
for(int i = 0 ; i < n/2 ; i++){
    swap(arr[i] , arr[n-i-1]) ;
}
```
:::spoiler `答案`
將陣列反轉，$i$ 從 $0\sim (\displaystyle\frac n2-1)$，因此時間複雜度$O(n)$。
:::

$13.$
```cpp=
int n ;
int arr[10000] ;
for(int i = 0 ; i < 10000 ; i++){
    arr[i] = i + 1 ;
}
cout << arr[n] ;
```
:::spoiler `答案`
不論 $n$ 為多少，這段程式碼的執行次數皆為 $10000$ ( + $1$ 次查詢)，因此為常數時間 $O(1)$。
:::

$14.$
```cpp=
int a = 0 ;
int s(int n) {
    int ans = 1 ;
    for(int i = 2 ; i <= n ; i++){
        ans *= i ;
    }
    return ans ; 
}

void f(int n ,bool flag) {
    if(flag == true) {
        a++ ;
        return ;
    }		
    for(int i = 1 ; i <= s(n) ; i++){
        f(n , true) ;	
    }
}
int main(){
    int n ;
    cin >> n ;
    f(n , false) ;
    cout << a ; 
}
```
:::spoiler `答案`
$s(n)$ 是計算 $n!$ ，時間複雜度為 $O(n)$。
$f(n,\ flag)$ 會進到 `for` 迴圈，每一輪都只有 $O(1)$，但在 `i<=s(n)` 每輪都需重新計算 $s(n)$，共計算 $s(n)=n!$ 次。
時間複雜度為 $O(n\times n!)$。
:::

