Big Omega (Ω) และ Big Thera (θ) Notation

สัญลักษณ์แสดงอาการ

เครื่องหมาย Asymptotic ใช้เพื่อแสดงถึงความซับซ้อนของอัลกอริธึมสำหรับการวิเคราะห์เชิง asymptotic สัญกรณ์เหล่านี้เป็นเครื่องมือทางคณิตศาสตร์เพื่อแสดงถึงความซับซ้อน มีสัญลักษณ์สามแบบที่ใช้กันทั่วไป

สัญลักษณ์บิ๊กโอเมก้า

สัญกรณ์ Big-Omega (Ω) ให้ขอบเขตที่ต่ำกว่าสำหรับฟังก์ชัน f(n) ถึงภายในปัจจัยคงที่

เราเขียน f(n) =Ω(g(n)) หากมีค่าคงที่บวก n0 และ c เช่นนั้น ทางด้านขวาของ n₀ f(n) อยู่บนหรือเหนือ c*g(n) เสมอ

Ω(g(n)) ={ f(n) :มีค่าคงที่ที่เป็นบวก c และ n0 เช่นนั้น 0 ≤ c g(n) ≤ f(n) สำหรับ n ≤ n₀ ทั้งหมด }

สัญลักษณ์ Theta ขนาดใหญ่

สัญกรณ์ Big-Theta(Θ) กำหนดขอบเขตของฟังก์ชัน f(n) ถึงภายในปัจจัยคงที่

เราเขียน f(n) =Θ(g(n)) หากมีค่าคงที่บวก n0 และ c₁ และค₂ ไปทางขวาของ n₀ f(n) อยู่ระหว่าง c₁ . เสมอ *g(n) และ c₂ *g(n) รวมอยู่ด้วย

Θ(g(n)) ={f(n) :มีค่าคงที่ที่เป็นบวก c₁ , c₂ และ n₀ เช่นนั้น 0 ≤ c₁ ก.(n) ≤ f(n) ≤ c₂ g(n) สำหรับ n ทั้งหมด ≥ n₀ }