---
# System prepended metadata

title: 競試必勝C++ 第二冊 演算法
tags: [C++]

---

# 必勝C++ 第二冊 演算法

## 漸進表示符
> 用於評估演算法的複雜度 *(Complexity)* 的表示方法
### Big $\Theta$
>用來表述演算法複雜程度的上限下限的集合
>雖然Big $\Theta$提供更精確的描述，但普遍在進行複雜度的評估時並不常被使用，故在此省略
### Big $O$
>在談論複雜度是最常使用的就是Big $O$
>定義:
>$$O(g(n))= \{ f(n)：存在正整數:c,n_0 ,並且對於所有n\geq n_0,滿足 0\leq f(n) \leq cg(n) \}$$
>由 $(0\leq f(n)\leq cg(n))$ 可以得知Big $O$表示依複雜度的上限 ***(upper bound)***
>在進行複雜度的估算時可以忽略常數因子和低階項，只計算最高階項，因為其影響了函數的增長速度。
### Big $\Omega$
>定義:
>$$\Omega(g(n))=\{f(n)：存在正整數:c,n_0,並且對於所有n\geq n_0,滿足0\leq cg(n)\} $$
>由 $(0\leq  cg(n) \leq f(n))$ 可得知Big $\Omega$ 與Big O相反，用於表示複雜度的下限 ***(lower bound)***


## 遞迴 (Recursive)
就遞迴，動態規劃的基礎，將一個問題拆分成多個性質相同的子問題，透果子問題解決子問題。如等差數列:
一長度為$n$的等差為$i$的數列，${X_n = X_{n-1} + i}$

## 貪婪 (Greedy)

## DP動態規劃 (Dynamic Programming)

## DFS深度優先搜索 (Depth First Search)

## BFS廣度優先搜索 (Breadth First Search)
***--Written By Chen***