[Algorithm] Asymptotic Notations 漸進符號｜Complexity 複雜度

Asymptotic notations are the mathematical notations that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

O(Big O) Notation

\begin{align}
& f(x) = O(g(x)) \\
& \text{iff} \quad \exists x_0, M > 0 \quad \text{s.t.} \quad \forall x[x > x_0 \ \Rightarrow \ \left| f(x) \right| < M \left| g(x) \right|] \\
& \\
& \text{iff} \ : \ \text{若且唯若 (if and only if)} \\
& \text{s.t.} \ : \ \text{使得 (such that)} \\
& \forall x( ～ ) \ / \ \forall x[ ～ ] \ / \ \forall x\{ ～ \} \ : \ \text{對所有的 } x \text{ 皆滿足 } ～ \\
& \text{※ 選擇使用中括號，只是因為 } f(x) \text{ 和 } g(x) \text{ 將小括號使用了}
\end{align}

Ω(Big Omega) Notation

\begin{align}
& f(x) = O(g(x)) \\
& \text{iff} \quad \exists x_0, M > 0 \quad \text{s.t.} \quad \forall x[x > x_0 \ \Rightarrow \ 0 < M \left| g(x) \right| < \left| f(x) \right|] 
\end{align}

Θ(Big Theta) Notation

\begin{align}
& f(x) = O(g(x)) \\
& \text{iff} \quad \exists x_0, M_1, M_2 > 0 \quad \text{s.t.} \quad \forall x[x > x_0 \ \Rightarrow \ 0 < M_1 \left| g(x) \right| < \left| f(x) \right| < M_2 \left| g(x) \right|] 
\end{align}

o(Littel O) Notation

\begin{align}
& f(x) = O(g(x)) \\
& \text{iff} \quad \forall M > 0, \ \exists x_0 > 0 \quad \text{s.t.} \quad \forall x[x > x_0 \ \Rightarrow \ \left| f(x) \right| < M \left| g(x) \right|] 
\end{align}

ω(Littel Omega) Notation

\begin{align}
& f(x) = O(g(x)) \\
& \text{iff} \quad \forall M > 0, \ \exists x_0 > 0 \quad \text{s.t.} \quad \forall x[x > x_0 \ \Rightarrow \ 0 < M \left| g(x) \right| < \left| f(x) \right|] 
\end{align}

Last Updated on 2023/08/16 by A1go