Page 20 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 20
2-10 โครงสร้างข้อมูลและขั้นตอนวิธี
บทน ิยามน้ีบ อกได้ว่า อัตราการเติบโตของ f(x) มากกวา่ ห รอื เทา่ กบั อัตราการเติบโตของ g(x) หรือเป็นการบอก
ขอบเขตลา่ ง (lower bound) ของอัตราก ารเติบโตข อง f(x) ภาพที่ 2.3 ข. แสดงค วามส ัมพันธ์โดยอ าศัยบ ๊ิกโอเมกาเพ่ือ
บอกขอบเขตล ่างของฟ ังก์ชัน f(x) เมื่อ x มีค่าม ากๆ จะได้ f(x) มีค่าอยู่เหนือกว่าห รือเท่ากับค ่าของ cg(x)
ตัวอย่างที่ 2.3 จงแ สดงว่า 5x2 เป็น Ω(x)
วธิ ที �ำ
สังเกตว ่า เมื่อ x > 1 จะได้ว่า 5x2 > x
ดังนั้น c = 1 และ x0 = 1 เป็นต ัวยืนย ันส �ำหรับค วามส ัมพันธ์ 5x2 = Ω(x)
3. บกิ๊ ทตี า
การพ ิจารณาหาท้ังขอบเขตบนแ ละขอบเขตล ่างข องก ารเติบโตของฟ ังก์ชัน สามารถอ ธิบายได้ด ้วยสัญลักษณ์
บ๊ิกทีตา (big teta) และส ามารถเขียนเป็นบทน ิยามท างคณิตศาสตร์ได้ ดังน้ี
บทนิยาม 2.3 บิ๊กท ตี า (Ѳ)
ฟังก์ชัน f(x) สามารถป ระมาณขอบเขตบนแ ละล่างได้ด ้วยบ ิ๊กทีต าของ g(x) เขียนแ ทนด ้วย
f(x) = Ѳ(g(x)) ถ้ามีค่าคงตัวบวก c1 ≥ 0 c2 ≥ 0 และ x0 ≥ 0 ที่ทำ�ให้ c1|g(x)| ≤ |f(x)| ≤ c2|g(x)|
เมื่อ x ≥ x0
บทน ิยามน ี้บ อกได้ว่า อัตราการเติบโตของ f(x) เท่ากับหรอื อยู่ในขอบเขตของอ ัตราก ารเติบโตข อง g(x) โดยมี
ค่าคงตัวเป็นปัจจัย หรือเป็นการบอกขอบเขตจ�ำกัดท้ังบนและล่างของ f(x) ภาพท่ี 2.3 ค. แสดงความสัมพันธ์บ๊ิกทีตา
ของฟังก์ชัน f(x) กับ g(x) ทุกค่า x ท่ีมีค่ามากกว่า x0 ค่าของ f(x) อยู่เหนือหรือเท่ากับ c1g(x) และอยู่ใต้หรือเท่ากับ
c2g(x)
ข้อสังเกต สามารถก ล่าวได้ว ่า f(x) = Ѳ(g(x)) ก็ต ่อเมื่อ f(x) = O(g(x)) และ f(x) = Ω(g(x)) นั่นเอง
ดังนั้น กล่าวโดยส รุปได้ว่า f(x) = O(g(x)) แสดงว ่า รับป ระกันว่าฟ ังก์ชัน f(x) โตในอัตราท่ีช ้ากว่า g(x) ดังน้ัน
g(x) จึงเป็นข อบเขตบนของ f(x) หรืออ ีกในหนึ่งสามารถก ล่าวได้ว ่า g(x) = Ω(f(x)) ซ่ึงห มายความว ่า f(x) เป็นขอบเขต
ล่างข อง g(x) น่ันเอง
เช่น x3 โตเร็วกว่า x2 ดังน ้ัน กล่าวได้ว่า x2 = O(x3) หรือ x3 = Ω(x2) น่ันเอง
ในทางเทคนิค ถ้าสมมติว่า f(x) = 2x2 แล้ว f(x) = O(x4) f(x) = O(x3) หรือ f(x) = O(x2) ได้ทุกตัว บิ๊กโอ
ท่ีดีท่ีสุดหรือเรียกว่าเหมาะสมท่ีสุด คือ f(x) = O(x2) เน่ืองจากเป็นการประมาณท่ีใกล้เคียงที่สุด และสามารถหาการ
ประมาณท ี่ด ีท ี่สุดแ ละเหมาะท ี่สุดในท�ำนองเดียวกันก ับส ัญลักษณ์อื่นๆ ได้
สมมติว่า f(x) = Ѳ(x2) จึงไม่ใช่เพียงการบอกขอบเขต แต่ยังเป็นการบอกการประมาณที่ดีท่ีสุด (ที่ใกล้เคียง
ที่สุด) เท่าท ่ีจะเป็นไปได้ให้ด้วย
