Understanding Big Θ (Theta) and Big Ω (Omega) in Asymptotic Notations-day 5

2024 iThome 鐵人賽

DAY 5

佛心分享-IT 人自學之術

演算法與資料結構入門：30天基礎學習之旅系列第 5 篇

16th鐵人賽

dc88

2024-09-19 00:33:51

172 瀏覽

分享至

上篇提到 Big O Notation
我們現在知道了 Big O 用來表示演算法的 upper bound / worst case scenario（上界限 / 最壞情況）
這篇介紹 Asymptotic Notations (漸進符號)，也就是 Big O 其背後的基本概念

Asymptotic Notations 漸進符號

Asymptotic notation helps us describe the efficiency of an algorithm by focusing only on the most significiant factors that impact its performance. It ignores constant factors and lower-order terms, allowing us to concentrate on how the algorithm scales as the input size grows.

漸進符號的意思就是，只關注影響演算法效率中最重要的部分，忽略掉常數因子或低階數項

upper bound & lower bound

Big Θ(Theta)

The Big Theta combination with Big O(upper bound) & Big Omega(lower bound)

Big Θ(Theta) 描述了由 Big O (upper bound)與 Big Ω (lower bound)組合而成的區間，表示該演算法最佳情況不會低於某值，但最糟情況也不會高於某值

This notation describes BOTH the upper and lower bound of a function and is often referred to as the average time complexity.

E.g
if an algorithm's time complexity is Θ(n), it means that

The algorithm will not take more than O(n) time (upper bound).
It will also not take less than Ω(n) time (lower bound).

Big Ω(Omega)

Describes the lower bound on the time complexity, or the best-case scenario.
若想知道此f(n)最少需耗費多少時間，用 Big Ω來取得此 f(n) 的 lower bound

還意猶未盡的話可以看這裡關於 Big O & Big Omega 的正式定義

definition of Big O

Definition Big–O, O()): Let f(n) and g(n) be functions that map positive integers to positive real
numbers. We say that f(n) is O(g(n)) (or f(n) ∈ O(g(n))) if there exists a real constant c > 0 and there
exists an integer constant n0 ≥ 1 such that f(n) ≤ c ∗ g(n) for every integer n ≥ n0.

definition of Big Omega

Definition (Big–Omega, Ω()): Let f(n) and g(n) be functions that map positive integers to positive
real numbers. We say that f(n) is Ω(g(n)) (or f(n) ∈ Ω(g(n))) if there exists a real constant c > 0 and
there exists an integer constant n0 ≥ 1 such that f(n) ≥ c · g(n) for every integer n ≥ n0.