複雜度

複雜度是定性描述該演算法執行成本（時間/空間）函式，用來分析演算法的效率。

常用函數

• Big $O$ 用來表示一個複雜度的上界，定義為 $f(n)\in O(g(n))\ iff\ \exists\ c,N\in R^{+},\forall n \geq N$ 有 $|f(n)| \leq |cg(n)|$ ，例如 $f(n)=5n^2+4n+1$ ，我們會注重最高項 $5n^2$ ，且我們會 5 是常數，得出 $f(n)\in O(n^2)$
• Big $\Omega$ 用來表示一個複雜度的下界，對於任意的 $f(n) \in O(g(n))$ , 都有 $g(n) \in \Omega (f(n))$ 。
• Big $\Theta$ 要同時滿足 Big $O$ 和 Big $\Omega$

Big $O$ 是我們比較常用的，其他兩個可能再一些地方會用到

常見複雜度

$O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)$ 另外還有一個在並查集常見，即 $O(\alpha(n))$ ，近似於 $O(1)$ ，可直接當作 $O(1)$

時間/空間複雜度

• 時間複雜度：和運算有關， *% 會比 +- 還要久，而複雜度得項次會跟迴圈有關，初階競賽只會在意你的項次，只要不要太大基本都會過，進階些比賽，有可能出現常數過大，導致複雜度合理卻還是吃 TLE 的情況，這時候需要利用 "壓常數" 技巧，降低時間，讓程式 AC。
• 空間複雜度：則是跟你宣告的變數記憶體總和有關，比時間複雜度容易估計，在樹狀的資料結構，往往需要搭配動態記憶體，才不會因為開太多空間而吃了 MLE。

題外話，如果你在你的 array 不是開在全域內，開了 10 的 5,6 次，在執行時跑出 RE，那你有以下兩種解決方式

• 把 array 移至全域
• 加上 static，表示靜態變數