Page 21 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 21
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-11
4. ลติ เทิลโอแ ละลิตเทิลโอเมกา
การหาขอบเขตด้วยบิ๊กโอและบิ๊กโอเมกา เรียกว่า เป็นการหาขอบเขตแบบรัดกุม (asymptotically tight)
เม่ือการป ระมาณมีอันดับเดียวกัน เช่น 2x2 = O(x2) เป็นการห าขอบเขตแบบร ัดกุม เพราะเป็นการประมาณท ่ีมีอ ันดับ
เท่าเทียมกันคือ 2x2 = O(x2) และ x2 = O(2x2) ด้วย แต่ 2x2 = O(x3) ไม่เป็นการหาขอบเขตแบบรัดกุม เน่ืองจาก
x3 ≠ O(2x2) จึงมีนิยามการประมาณขอบเขตอีก 2 แบบ ท่ีใช้อธิบายขอบเขตแบบไม่รัดกุม (not asymptotically
tight) ได้ด ังต่อไปน ี้
บทนยิ าม 2.4 ลติ เทิลโอ (o)
ฟังก์ชัน f(x) สามารถประมาณข อบเขตบ นแบบไม่ร ัดกุมได้ด ้วยบ ิ๊กทีตาของ g(x) เขียนแทนด้วย
f(x) = o(g(x)) สำ�หรับท ุกค่าค งตัวบวก c ≥ 0 ถ้ามี x0 ≥ 0 ที่ทำ�ให้ |f(x)| < c|g(x)| เมื่อ x ≥ x0
บทนิยามน้ีบอกได้ว่า อัตราการเติบโตของ f(x) นอ้ ยกว่าอัตราการเติบโตของ g(x) ซ่ึงเป็นบทนิยามท่ีต่างจาก
บ๊ิกโอตรงที่บ ิ๊กโออ นุญาตให้มีอัตราการเติบโตที่เท่ากันได้ บิ๊กโอจึงใช้บอกขอบเขตบนได้ท้ังแบบรัดกุมและไม่รัดกุม แต่
ลิตเทิลโอบอกได้เฉพาะขอบเขตบนแบบไม่ร ัดกุม หรือกล่าวอีกอย่างหน่ึงได้ว่า f(x) = o(g(x)) ถ้า f(x) = O(g(x)) และ
f(x) ≠ Ѳ(g(x))
บทน ยิ าม 2.5 ลติ เทลิ โอเมก า (ω)
ฟังก์ชัน f(x) สามารถประมาณข อบเขตล่างแบบไม่ร ัดกุมได้ด ้วยบิ๊กท ีตาของ g(x) เขียนแทนด ้วย
f(x) = ω(g(x)) สำ�หรับท ุกค ่าคงตัวบ วก c ≥ 0 ถ้าม ี x0 ≥ 0 ที่ท ำ�ให้ |f(x)| > c|g(x)| เมื่อ x ≥ x0
บทนิยามน้ีบอกได้ว่า อัตราการเติบโตของ f(x) มากกว่าอัตราการเติบโตของ g(x) เช่นเดียวกันบิ๊กโอเมกาใช้
บอกขอบเขตล่างได้ทั้งแบบรัดกุมและไม่รัดกุม แต่ลิตเทิลโอเมกาบอกได้เฉพาะขอบเขตล่างแบบไม่รัดกุม หรือกล่าว
อีกอย่างหน่ึงว่า f(x) = ω(g(x)) ถ้า f(x) = Ω(g(x)) และ f(x) ≠ Ѳ(g(x))
ตัวอย่างท่ี 2.4 จงห าบ๊ิกโอ บ๊ิกโอเมก า บิ๊กท ีตา ลิตเทิลโอ และล ิตเทิลโอเมกา ของ f(x) = 4x5
วิธที �ำ
ถ้าให้ x > 0 จะได้ว ่า 3x5 < 4x5 < 5x5
สังเกตว ่า f(x) < 5x5 cx5
ดังน ั้น f(x) = O(x5) จากบ ทน ิยามบ ๊ิกโอ เมื่อ x0 = 0 และ c = 5 จะได้ว ่า f(x) ≤ เมื่อ x > x0
สังเกตว ่า 3x5 < f(x) จากบ ทน ิย ามบิ๊กโอเมกา เมื่อ x0 = 0 และ c = 3 จะได้ว ่า cx5 ≤ f(x) เมื่อ x > x0
ดังน ้ัน f(x) = Ω(x5)
สังเกตว่า 3x5 < 4x5 < 5x5 จากบ ทนิย ามบ ๊ิกโอเมก า
จะได้ว ่า 3x5 ≤ f(x) ≤ 5x5 เม่ือ x0 = 0 และ c1 = 3 c2 = 5
ดังน ้ัน f(x) = Ѳ(x5)
เม่ือ x > x0
สังเกตว่า 4x5 < cx6 ส�ำหรับท ุกๆ ค่าค งตัวบ วก c และเม่ือ x0 = 0 จากบ ทน ิยามลิตเทิลโอ
จะได้ว่า f(x) < cx6 เมื่อ x > x0
