# 時間複雜度概述
## -
----
Q：什麼是時間複雜度？
A：描述程式執行時間的函式
----
$O(f(n)), o(g(n)), Θ(h(n)), Ω(i(n))$
常使用$O(f(n))$表示，唸作Big-O，其他先不提
----
Define $O(f(n))$： 當資料量為$n$時，
程式執行時間不超過$f(n)$的常數倍
----
$If\ g(x)=O(f(x)),∃ M,x_0>0,$
$such\ that\ ∀x≥ x_0,then\ |g(x)|≤M|f(x)|$
----
計算原則
* 每種操作(加減乘除模、賦值、條件判斷...)都當成一單位時間
* 常數倍數不計
* 如果將程式分成兩段複雜度，總複雜度取較大的那段(低次項不計)
* 若$O(f(n))$的程式執行$g(n)$次，總複雜度為兩者相乘，即$O(f(n)*g(n))$
----
試估算以下程式碼的時間複雜度
```cpp
int n,i=0,j=0;
cin >> n;
while(i<n){
while(j<i){
j++;
}
i++;
}
```
總複雜度： $O(N^2)$
---
### APCS出題模式
前兩題通常不需考慮複雜度，
後兩題需要估算複雜度。
----
| n | 過萬 | 數千 | 數百 | 20~25 | 10 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 複雜度 | $O(n)$ or $O(nlog(n))$ | $O(n^2)$ | $O(n^3)$ | $O(2^n)$ | $O(n!)$ |
----
Judge平均速度為$10^8$，
只要將範圍帶入估計複雜度除以$10^8$
即可預測執行時間，
判斷是否會超時(TLE)
---
例題一
----
Q: 給 $t$ 個正整數 $x_i$，判斷 $n$ 是否為質數。
其中 $1\le t \le 100,\ 1 \le x_i \le 10^{10}$
----
試除法
Solution 總複雜度 $O(T\sqrt {x_{max}})$
```cpp=
#include<iostream>
#include<cmath>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
long long x;
cin >> x;
if(x==1){
cout << "No\n";
continue;
}
long long s = sqrt(x+0.5);
bool chk = true;
for(int i=2;i<=s;i++) if(x%i==0) {
chk = false;
break;
}
if(chk) cout << "Yes\n";
else cout << "No\n";
}
return 0;
}
```
---
例題二
----
Q: 給 $t$ 個正整數 $x_i$，判斷 $n$ 是否為質數。
其中 $1\le t \le 10^6,\ 1 \le x_i \le 10^{6}$
----
突破口：$N$比較小，知道$1 \sim 10^6$是不是質數就好！
----
篩法
-----
~~1~~ 2 3 ~~4~~ 5 ~~6~~ 7 ~~8~~ ~~9~~ ~~10~~
11 ~~12~~ 13 ~~14~~ ~~15~~ ~~16~~ 17 ~~18~~ 19 ~~20~~
複雜度：$\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + ...$
----
引理： $1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N} = O(log(N))$
$\to$篩法複雜度取上界
$\frac{N}{2} + \frac{N}{3} + \frac{N}{5} + ... \le N(1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{N})=O(NlogN)$
作法：用$O(KlogK)$建質數表，以$O(1)$回答詢問
總複雜度：$O(KlogK+t), K=10^6,t\le10^6$
----
Solution
```cpp=
#include<iostream>
using namespace std;
const int K = 1e6+2;//1000002.0
int isPrime[K];
int main(){
for(int i=2;i<=K;i++) isPrime[i]=1;
for(int i=2;i<=K;i++){
if(isPrime[i]==1){
for(int j=i*2;j<=K;j+=i) isPrime[j]=0;
}
}
int T,x;
cin >> T;
while(T--){
cin >> x;
cout << (isPrime[x]?"Yes\n":"No\n");
}
}
```
---
例題三
----
Q: 給你一個只包含小寫字母的字串$S$，
請找出最短子字串包含所有小寫字母，
如果有多個子字串，請輸出第一次出現的，
如果不存在這種子字串則輸出NA。
其中$| S | \le 10^6$
----
直覺: 枚舉子字串左界$L$($O(n)$)，向右一直延伸右界$R$直到區間包含所有小寫字母為止($O(n)$)，
總複雜度$O(n^2)$，太大！
----
優化: $L$向右一格後將原本$L$的字母次數減一，$R$就能直接從原本的地方繼續掃，複雜度變成$O(n)$
----
Solution
```cpp=
#include<iostream>
#include<cstring>
using namespace std;
int frq[202],now;
int main(){
string S;
cin >> S;
int N = S.length(),L=-1,minLen=1e7;
for(int l=0,r=0;l<N;l++){
while(now<26&&r<N){
char c = S[r++];
if(!frq[c) now++;
frq[c]++;
}
if(now==26&&minLen>r-l){
minLen = r-l;
L=l;
}
if(l<r){
char c = S[l];
frq[c]--;
if(!frq[c]) now--;
}
}
cout << (L==-1?"Na":S.substr(L,minLen)) << endl;
}
```
{"metaMigratedAt":"2023-06-16T23:25:44.807Z","metaMigratedFrom":"YAML","title":"時間複雜度概述","breaks":true,"contributors":"[{\"id\":\"ec85c8ff-a359-4b91-ac52-120dad52b91f\",\"add\":3588,\"del\":275}]"}