算法筆記-時間複雜度概述

• 算法筆記目錄

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

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

對於$O()$，有以下定義：
$$ Def:\
\qquad 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))$。