時間複雜度與漸近分析

(一) Big-O nontation (asymptotic tight upper bound)

• 定義: if and only if f(n)=O(g(n)), 則存在有正數常數 c, n₀，使 n>n₀ 時 |f(n)| ≤ c×|g(n)|
• 用來表示函數 f(n) 複雜度等級的緊密上限為 g(n)
• f(n)=O(g(n))，表示函數 f(n) 的複雜度等級不超過 g(n)
• f(n)=O(g(n))，f(n) ≤ g(n)

(二) Big-Ω nontation (asymptotic tight lower bound)

• 定義: if and only if f(n)=Ω(g(n)), 則存在有正數常數 c, n₀，使 n>n₀ 時 |f(n)| ≥ c×|g(n)|
• 用來表示函數 f(n) 複雜度等級的緊密下限為 g(n)
• f(n)=O(g(n))，表示函數 f(n) 的複雜度等級不低於 g(n)
• f(n)=O(g(n))，f(n) ≥ g(n)

(三) Θ nontation (asymptotic tight bound)

• 定義: if and only if f(n)=Θ(g(n)), 則存在有正數常數 c₁, c₂, n₀，使 n>n₀ 時 c₁×|g(n)| ≤ |f(n)| ≤ c₂×|g(n)|
• 用來表示函數 f(n) 複雜度等級的緊密界限為 g(n)
• f(n)=Θ(g(n))，表示函數 f(n) 的複雜度等級與 g(n) 相同
• f(n)=Θ(g(n))，f(n) ~ g(n)

(四) little-o nontation (untight upper bound)

• 定義: if and only if f(n)=o(g(n)), 則對任意常數 c > 0 皆存在常數 n₀ 使 n>n₀ 時 |f(n)| < c×|g(n)|
• f(n)=o(g(n))，表示函數 f(n) 的複雜度等級低於 g(n)
• f(n)=o(g(n))，f(n) < g(n)

(五) little-ω nontation (untight lower bound)

• 定義: if and only if f(n)=ω(g(n)), 則對任意常數 c > 0 皆存在常數 n₀ 使 n>n₀ 時 |f(n)| > c×|g(n)|
• f(n)=ω(g(n))，表示函數 f(n) 的複雜度等級高於 g(n)
• f(n)=ω(g(n))，f(n) > g(n)