# 簡介
是一種方便計算程式執行時間的方法，寫題目時算好時間複雜度並只適合的做法可以減少 $TLE$ 的機率。
符號為 $O(~~)$ ，通常以 $n$ 當作變數。
# 時間頻度
哪個演算法中語句執行次數多，他花費時間就多，而一個演算法中的語句執行次數稱為時間頻度，記為 $T(n)$ ，即為定義為任何大小的輸入 $n$ 所需的最大執行時間。
若 $T(n)=O(n^2)$，則代表 $T(n)$ 最差執行時間不超過 $O(n^2)$。
# 計算
在講之前要先說，當 $n$ 趨向無限大時，有三個需要忽略的：
## 忽略常數項
$2n+20$ 和 $2n$ 隨著 $n$ 變大，執行曲線無限接近，$20$ 可以忽略。
$3n+10$ 和 $3n$ 隨著 $n$ 變大，執行曲線無限接近，$10$ 可以忽略。
## 忽略低次項
$2n^2+3n+10$ 和 $2n^2$ 隨著 $n$ 變大，執行曲線無限接近，可以忽略 $3n+10$。
$n^2+5n+20$ 和 $n^2$ 隨著$n$ 變大，執行曲線無限接近，可以忽略 $5n+20$。
## 忽略係數
隨著 $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)$。
:::
## 常見時間複雜度
* 常數階 $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!)$。
:::
Sign in with Wallet
Connect another wallet