---
# System prepended metadata

title: DS_BigONotation
tags: [CYCS_DS]

---

# DS Big O Notation

* 以下文章來源為 [本網站內容：https://ja-errorpro.codes/posts/1/algo-runtime/](https://ja-errorpro.codes/posts/1/algo-runtime/)
* 其中有部分內容有修改

時間複雜度在競程中是個非常重要且最基本的工具，  
係用於估算程式執行N次，大概需要花多久時間。

我們在程式中做的任何事情可能都需要花費1單位時間，  
比如五則運算、條件判斷、變數存賦等。  
而我們通常會使用函式$O(Big-O)$ 來表示程式的複雜度。  

對於$O()$，有以下定義：  
$$
   If\ f(x) = O(g(x)),\ ∃M,x_0 > 0,\ such \ that \ ∀x>=x_0,then \ |f(x)| <= M|g(x)|
$$

為什麼我們需要估時間複雜度？  
因為我們在寫程式追求的是速度！當你的演算法太慢(時間複雜度太大)時，  
就算結果是對的，但你會在Online Judge上或APCS得到一個TLE(Time Limit Exceeded)，  
即若將測資丟到你的程式，會超出該題目所規定的執行時間。

要如何估自己的程式會跑幾秒？  
通常，Judge的執行速度大約是1e8筆/秒，因此只要將題目的範圍限制代入所估複雜度，  
然後除以1e8，就能大概知道自己程式會不會TLE了。

常見的複雜度有： $1,n,n^2,n^3,nlogn,2^n$。
而log通常以2為底但我們不太會去明指以誰為底。  

以下是複雜度計算的原則：

-- 1.常數倍數不計( $O(2n) = O(n) = O(3n)$ )。  

-- 2.若將程式分成兩段複雜度為$O(f(n)),\ O(g(n))$,總複雜度就取複雜度比較大的那段。  
  即$O(f(n)+g(n)) = O(f(n)) > O(g(n)) ? O(f(n)) : O(g(n))$  
  
-- 3.若有一段程式複雜度為$O(f(n))$執行$g(n)$次，總複雜度是$O(f(n)*g(n))$。  