Asymptotic Notations (สัญกรณ์渐近)
ใช้แทนความซับซ้อนอัลกอริทึมสำหรับการวิเคราะห์渐近 มี 3 สัญกรณ์หลัก
Big-Omega Notation (Ω) - ขอบเขตล่าง
Big-Omega (Ω) ให้ขอบเขตล่าง (Lower Bound) ของฟังก์ชัน f(n) ภายในตัวคูณคงที่
f(n) = Ω(g(n)) หากมีค่าคงที่บวก n₀ และ c ทำให้ทางขวาของ n₀ f(n) อยู่บนหรือสูงกว่า c·g(n) เสมอ
Ω(g(n)) = { f(n) : มีค่าคงที่บวก c, n₀ ที่ทำให้ 0 ≤ c·g(n) ≤ f(n) สำหรับทุก n ≥ n₀ }
Big-Theta Notation (Θ) - ขอบเขตแน่น
Big-Theta (Θ) ให้ขอบเขตทั้งบนและล่าง (Tight Bound) ของฟังก์ชัน f(n)
f(n) = Θ(g(n)) หากมีค่าคงที่บวก n₀, c₁, c₂ ทำให้ทางขวาของ n₀ f(n) อยู่ระหว่าง c₁·g(n) และ c₂·g(n) เสมอ
Θ(g(n)) = { f(n) : มีค่าคงที่บวก c₁, c₂, n₀ ที่ทำให้ 0 ≤ c₁·g(n) ≤ f(n) ≤ c₂·g(n) สำหรับทุก n ≥ n₀ }
