Page 19 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 19
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-9
cg(x) f(x) c2g(x)
f(x) cg(x) f(x)
x> ≤x0 cg(x) xcg>(xx)0≤ f(x) c1g(x)
f(x)
fx(x0) = Ω(g(x)) x0cx1f>(gx()xx=0) ≤Ѳf((gx()x)≤) c2g(x)
x0 f(x) = O(g(x)) x ข. x ค.
ก.
ภาพท ี่ 2.3 กราฟตัวอยา่ งเพ่ืออ ธิบายความหมายข อง บก๊ิ โอ บิ๊กโอเมก า และบิ๊กทีตา
ภาพท่ี 2.3 เป็นกราฟตัวอย่างเพ่ืออธิบายความหมายของบ๊ิกโอ (O) บ๊ิกโอเมกา (Ω) และบิ๊กทีตา (Ѳ) ตาม
ล�ำดับ โดยค่า x0 ในแต่ละส่วนจะเป็นค่าท่ีน้อยท่ีสุดที่เป็นไปได้ที่ค่าอื่นใดๆ ท่ีมากกว่า x0 จะท�ำให้ความสัมพันธ์ใน
แต่ละสัญลักษณ์เป็นจริง
ภาพที่ 2.3 ก. บิ๊กโอ (O) ให้ขอบเขตบนของฟังก์ชันภายใต้ค่าคงตัวท่ีเป็นปัจจัยหลัก เขียนแทนด้วย f(x) =
O(g(x)) ถ้ามีค ่าค งตัวบ วก c และ x0 ท่ีท �ำให้ค ่าของฟังก์ชัน f(x) ท่ีอยู่ท างขวาของ x0 มีค่าอ ยู่ต ่ําก ว่าหรือเท่ากับค ่าของ
cg(x)
ภาพท ่ี 2.3 ข. บิ๊กโอเมก า (Ω) ให้ข อบเขตล ่างข องฟ ังก์ชันภ ายใต้ค ่าค งตัวท ่ีเป็นป ัจจัยห ลัก เขียนแ ทนด ้วย f(x)
= Ω(g(x)) ถ้ามีค่าคงตัวบวก c และ x0 ที่ท�ำให้ค่าของฟังก์ชัน f(x) ที่อยู่ทางขวาของ x0 มีค่าอยู่เหนือกว่าหรือเท่ากับ
ค่าของ cg(x)
ภาพที่ 2.3 ค. บิ๊กทีตา (Ѳ) ก�ำหนดขอบเขตของฟังก์ชันภายใต้ค่าคงตัวที่เป็นปัจจัยหลัก เขียนแทนด้วย
f(x) = Ѳ(g(x)) ถ้าม ีค่าคงตัวบ วก c1, c2 และ x0 ที่ท�ำให้ค ่าของฟังก์ชัน f(x) ท่ีอ ยู่ทางข วาของ x0 มีค่าอยู่ระหว่าง c1g(x)
และ c2g(x)
2. บ๊ิกโอเมก า
นอกจากจะมีการพิจารณาขอบเขตบนของการเติบโตของฟังก์ชันใดๆ แล้ว ในท�ำนองเดียวกันการพิจารณา
ขอบเขตล ่างของการเติบโตข องฟังก์ชัน สามารถอ ธิบายได้ด ้วยส ัญลักษณ์บ๊ิกโอเมกา (big omega) และส ามารถเขียน
เป็นบทนิยามทางค ณิตศาสตร์ได้ ดังนี้
บทนยิ าม 2.2 บกิ๊ โอเมก า (Ω)
ฟังก์ชัน f(x) สามารถป ระมาณข อบเขตล ่างได้ด ้วยบ ิ๊กโอเมกาของ g(x) เขียนแ ทนด ้วย
f(x) = Ω(g(x)) ถ้าม ีค ่าคงตัวบวก c ≥ 0 และ x0 ≥ 0 ที่ทำ�ให้ |f(x)| ≥ c|g(x)| เมื่อ x ≥ x0
