---
# System prepended metadata

title: 時間複雜度
tags: [課程]

---

---
###### tags: `課程`
---
時間複雜度
===
https://pse.is/3bb8vp

----

# 語法/算法

---

## 複雜度

----

##
做每件事情都有他的花費時間

- 長大一歲 需要365.25天
- 寫考卷可能需要 0.04天
- 寫10張考卷可能需要0.4天

----

### 時間複雜度
在執行一個程式的時候

根據輸入的數字範圍 所推估的時間長度

通常會是用多項式表示

----

ex. $4n^3+8n^2+4$

這個時候可以發現當$n$很大時

可以只注意$4n^3$ (後面成長速度太低)

又因為4是常數 所以可以忽略

最後得到 $O(n^3)$

----

### 空間複雜度

如同時間複雜度

拿來估計記憶體使用量

---

## 計算時間複雜度

----

## $O(1)$ 做一件事情
- 判斷true false
- 弄一個變數or賦值
- 輸入/出一個東西
- 公式計算1~N的總和($\frac{N(N-1)}{2}$)

----

## $O(N)$ 迴圈重複
- 印出1~N
- 暴力計算1~N的總和($1+...+N$)

----

## $O(N^2)$
雙重迴圈/其他
- 印出NN乘法表
- 重複O(N) N次
- 給二維陣列賦值
- 遞迴計算費氏數列

----

## 其他常見複雜度

- $\sqrt{N}$ 確定是否為質數
- $log(N)$ 快速排序

----

## 成長圖

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

---

## 搜尋

----

## 終極密碼
常見的猜數字遊戲 
從範圍(0-100)中猜出對方的數字
->策略 每次從範圍中找中間的數字

----

## 範例
[0,100]50 -> 太大
[0,50]25 -> 太小
[25,50]37 -> 太大
[25,37]31 -> 太大
[31,37]34 -> 太小
[34,37]36 猜對ㄌ

----

## 二分搜尋
對於一個排序過後的數列
如果要找數值x，可以用上面的方法

----

在arr中找出數字x在第幾個
```cpp=
l = 0, r = N;
mid =(l + r)/2
x < arr[mid] ? r = mid : l = mid
```

----

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

----

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

----

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

----

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

----

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


----

## CODE

```cpp=
int l = 0, r =n;
while (l != r - 1) {
    int mid = (l + r) / 2;
    if (x < arr[mid]) r = mid;
    else l = mid;
}
cout << "find:" << l <<endl;
```

----

## 簡單搜尋
```cpp=
for(int i = 0; i < n; i++){
    if(arr[i] == x){
        cout << "find:" << i << endl;
        break;
    }
}
```

----

## 時間複雜度！
二分搜尋每次可以減少一半的範圍
$N\Rightarrow\frac{N}{2}\Rightarrow\frac{N}{4}\Rightarrow\frac{N}{8}\Rightarrow...\Rightarrow\frac{N}{2^A}$
$2^A = N$
取$log_2 \Rightarrow log_22^A=log_2N$
$A = log_2N$
$O(log_2N):O(N)$

---

## 排序

----

## 選擇排序

{%youtube xWBP4lzkoyM %}

----

## CODE
```cpp=
for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
        if(arr[i] > arr[j]){
            swap(arr[i], arr[j]);
        }
    }
}
```
$O(N^2)$

----

## 合併排序
請看白板><

----

## 快速排序
{%youtube 5nXrEBhBFpU%}

----

## CODE

```cpp=
sort(arr, arr+n);
```

---

## 各種奇怪的排序影片
{%youtube kPRA0W1kECg %}

---

## 題目們

---

## 手寫一次二分搜

---

## 氣泡排序

---