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

สัญลักษณ์กำกับ

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

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

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

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

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

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

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

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

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

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

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

เราเขียน f(n) =Θ(g(n)) หากมีค่าคงที่บวกn0 และ c1 และ c2 เช่นนั้น ทางด้านขวาของ n0 f(n) จะอยู่ระหว่าง c1*g(n) และ c2*g เสมอ (n) รวม.

Θ(g(n)) ={f(n) :มีค่าคงที่ที่เป็นบวก c1, c2 และ n0 เช่นนั้น 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) สำหรับทุก n ≥ n0}