---
tags: 文華社課
---
> 文華高中電腦研究社29th
> 編輯 : 黃昱凱、陳睿哲
# C++從零入門Level 3-1
這章主要會講解常用且基本的演算法
會看看時間複雜度、排序、和貪婪演算法~
---
## 時間複雜度:Big O
現代人最關心的就是一個演算法的效率
要不然跑一個網頁3、4秒你受得了嗎w
但是我們很快發現
我們沒辦法準確的描述一個演算法的效率(用秒或毫秒為單位是不太適當的)
所以出現了Big O，大O符號來表示
規則是這樣的:
* 如果一個程式要跑**常數次**，如1次、8次或9999次，記做**O(1)**，又稱常數時間演算法
* 如果**資料數可變動，輸入n它會跑n次**、n+5次或8n次，記做**O(n)**，又稱線性時間演算法
* 其他，如果有指數位，**以最高次訂**，如跑n^2^次記做O(n^2^)，如跑n^3^+n次，**最高項n^3^，記做O(n^3^)**
通常我們的目標是將時間複雜度降到O(n)或O(nlog2(n))以下，這樣處理十萬筆資料通常不會超過要求(通常1秒)
對於演算法的題目，如果你用了太差/慢的程式或演算法，會出現超時(TLE)，然後就和分數say goodbey了，當然有些題目要求沒那麼嚴格，但至少不能寫出天真的程式w，像O(n^3^)這種一看大概就不行了w
關係圖:
橫軸為輸入資料大小、縱軸為所花時間
### 判讀
簡易的判讀方式是數有幾層巢狀迴圈
就是有層for迴圈包著for迴圈
像下面這是選擇排序法的程式
```cpp=
for(int i=0;i<n;i++){
int idx=i;
for(int j=i;j<n;j++){
if(arr[j]<arr[idx]){
idx=j;
}
}
swap(arr[i], arr[idx]);
}
```
你可以看到，它的for迴圈內還有一層for迴圈，時間複雜度O(n^2^)不算太好
但有時候也不一定，像掃描線演算法也會出現兩個for迴圈
```cpp=
for(int i = 0;i < n;i ++){//第一層
q.push(a[i]);
times[a[i]] ++;
if (times[a[i]] == 2){
int k = mp[a[i]] - cnt;
for(int i = 0;i <= k;i ++) {//第二層
q.pop();
cnt ++;
}
times[a[i]] --;
}
mp[a[i]] = i;
max_len = max(max_len, int(q.size()));
}
```
但是你可以數一下，整條掃描線只會由左至右掃一遍，也就是O(n)
所以說還是要以**實際執行的次數**來決定時間複雜度，看for迴圈不一定準，但一開始還OK
---
## 排序
換到竹科實中講義寫得很清楚(升序)
https://hackmd.io/@CLKO/ry9twDVpW?type=view
這些雖然都是簡單的概念
但基本上，應用問題才用得到
因為它們的時間複雜度都是O(n^2^)
另外有更快的演算法
ex:merge sort、heap sort ，都只要O(nlog(n))
但如果你的想法是這樣的w:
那就直接用STL的sort()
升序排列用法:
```cpp
int a[N];
//吃完資料後
sort(a, a+N);//sort(起點,終點);
```
降序排列用法:
```cpp
int a[N];
//吃完資料後
sort(a, a+N, greater<int>());//sort(起點,終點);
```
:::success
- [ ] [例題:a233排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)
tip:用STL sort就夠快囉~~
:::
:::success
- [ ] [例題:d190: 11462 - Age Sort](https://zerojudge.tw/ShowProblem?problemid=d190)
:::
---
:::
## 空間複雜度
基本上呢~ 和空間複雜度差不多的判讀方法-使用Big O
假設輸入資料長度為n，表示所使用的儲存空間大小
取**最高項次、並忽略係數**
試比較下面計算階乘的例子:
### 例1.
```cpp
#include<bits/stdc++.h>
using namespace std;
int factorial(int n){
int result = 1;
for(int i = 1;i <= n;i ++){
result *= i;
}
return result;
}
int main(){
int n;
cin >> n;
for (int i = 1;i <= n;i ++) cout << factorial(i);
}
```
在這個例子中計算(1~n)階乘的方法是
從1~n**呼叫n次函數，再經過n次計算**算出階乘
因此時間複雜度為**O(n^2^)**
空間複雜度因**沒有額外使用空間，為O(1)**
是**節省空間**但**花費時間**的演算法
### 例2.
```cpp
#include<bits/stdc++.h>
using namespace std;
vector <int> arr;
int factorial(int n){
int result = 1;
for(int i = 1;i <= n;i ++){
result *= i;
arr.push_back(result);
}
return result;
}
int main(){
int n;
cin >> n;
factorial(n);
for (int i = 0;i < n;i ++) cout << arr[i] <<endl;
}
```
然而在這個例子中，計算(1~n)階乘的方法是
**只呼叫一次函數，再經過n次計算**算出階乘
過程中將(1~n)階乘結果記錄在**長度為n**的陣列中
因此時間複雜度為**O(n)**
空間複雜度因使用長度為n的陣列(vector)，為**O(n)**
相對上一個程式是**節省時間**但**花費空間**的演算法
輸出結果都是一樣的，如下圖(第一行的8為輸入)
所以通常，**時間和空間複雜度是可以trade off的!**
依題目要求寫出程式，就要**看好題目給的時間和空間限制**
不過就像我們在時間複雜度那邊講的，時間通常是大家要求的
所以通常範例2是較佳的寫法
## 貪心演算法(greedy)
遇到求最大最小值時，每次選定當下最佳決策。
But 不保證其正確性(eg. 0/1背包問題)。
就算可以greedy，也要考慮依什麼標準做greedy(考慮反例)
思考問題是否能用最短視近利的方式解決
直接看題目八~
### 例題:換錢問題
蘿莉國有面額各為1000、500、100、50、10、5、1的鈔票
現在有一個人拿了n元
請輸出最少要給他幾張蘿莉國鈔票呢?
範例輸入1:
```
5050
```
範例輸出1:
```
6
```
範例輸入2:
```
5731
```
範例輸出2:
```
12
```
範例程式:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main()
{
int money[7] = {1000, 500, 100, 50, 10, 5, 1};
int n, total = 0, idx = 0;
cin >> n;
while(n != 0)
{
while(n >= money[idx])
{
n -= money[idx];
total ++;
}
idx ++;
}
cout << total <<endl;
}
```
這是一個greedy的經典例子
當考慮5050元時，直接先拿最大面額的鈔票數量會最少
拿5張1000後剩下50元
再拿一張50，即(5+1)張就是答案
像這種短視近利，每次只考慮最大或最小的問題就可以使用greedy
:::danger
- [ ] [進階題: APCS_2021_11_3生產線](https://zerojudge.tw/ShowProblem?problemid=g597)
提示:前綴和 排序 貪心法
:::
但是請試想一下，如果今天蘿莉國發行了7元面額的鈔票
貪心法是否還能算出正確的答案呢~?
哼哼~聰明如你，很快就發現答案是不行
那要怎麼辦?
就要使用之後會教到的動態規劃(DP)囉~
---
> 目錄: https://hackmd.io/@lolicon5208/HkSNa1kIY
> 補充: https://hackmd.io/2O2u-4Q0Sxu-ytDVwLIEog
## 參考答案
### a233
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[int(1e6+5)];
int main(){
int n;
cin >> n;
for(int i = 0;i < n;i ++) cin >> a[i];
sort(a, a+n);
for(int i = 0;i < n;i ++) cout << a[i] <<" ";
}
```
### d190
```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[int(2e6+5)];
int main()
{
int n;
while(cin >> n)
{
for(int i = 0; i < n; i ++) cin >> a[i];
sort(a, a+n);
for(int i = 0; i < n; i ++) cout << a[i] <<" ";
cout <<endl;
}
}
```
Sign in with Wallet
Connect another wallet