Asymptotic Notations คืออะไร?
Asymptotic Notations (สัญกรณ์渐近) ใช้แทนความซับซ้อนของอัลกอริทึมสำหรับการวิเคราะห์渐近 (Asymptotic Analysis) เป็นเครื่องมือทางคณิตศาสตร์สำหรับแทนความซับซ้อน มี 3 สัญกรณ์หลักที่ใช้กันทั่วไป
Big-Oh Notation (O) - ขอบเขตบน
Big-Oh (O) ให้ขอบเขตบน (Upper Bound) ของฟังก์ชัน f(n) ภายในตัวคูณคงที่
เราเขียน f(n) = O(g(n)) หากมีค่าคงที่บวก n₀ และ c ที่ทำให้ทางขวาของ n₀ ฟังก์ชัน f(n) จะอยู่บนหรือต่ำกว่า c·g(n) เสมอ
O(g(n)) = { f(n) : มีค่าคงที่บวก c และ n₀ ที่ทำให้ 0 ≤ f(n) ≤ c·g(n) สำหรับทุก n ≥ n₀ }
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₀ }
