Page 29 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 29
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-19
เรอ่ื งท ี่ 2.1.3
การเปรยี บเทียบก ารเตบิ โตข องฟ งั กช์ นั
การใช้สัญลักษณ์บิ๊กโอช่วยบอกขอบเขตบนของการเติบโตของฟังก์ชัน ซึ่งเป็นการเปรียบเทียบฟังก์ชันใน
ลักษณะห น่ึง นอกจากนี้แ ล้วการหาความส ัมพันธ์ข องอัตราการเติบโตของฟังก์ชัน 2 ฟังก์ชัน เพื่อเปรียบเทียบว่าฟ ังก์ชัน
f(x)
ไหนโตเร็วกว่า โดยปกติยังสามารถหาได้จากการเทียบฟังก์ชันท้ังสองโดยการค�ำน วนหาค่าลิมิต xl→im∞ g(x) ค�ำต อบ
ท ี่เป็นไปได้ท ้ังหมดมี 4 กรณีด ้วยก ัน คือ
0 f(x) เติบโตช ้ากว่า g(x) ดังนั้น f(x) = O(g(x)
xl→im∞ gf((xx)) = ∞k f(x) และ g(x) เติบโตแ บบเดียวกัน ดังน ั้น f(x) = θ(g(x))
f(x) เติบโตเร็วก ว่า g(x) ดังน ้ัน g(x) = O(f(x))
หาค่าไม่ได้ f(x) และ g(x) ไม่มีความส ัมพันธ์กัน
ตวั อยา่ งท่ี 2.13 ก�ำหนดให้ f(x) = 3x2 — 2x และ g(x) = x2 + 5x จงห าว ่าฟ ังก์ชันไหนโตเร็วก ว่ากัน
วธิ ที �ำ
f(x)
หา xl→im∞ g(x) ได้ด ังนี้
3x2 — 2x
xl→im∞ f(x) = xl→im∞ x2 + 5x
g(x)
= xl→im∞ x(3x — 2)
x(x + 5)
(3x — 2)
= xl→im∞ (x + 5)
= xl→im∞ 3 — xx25
1 +
= 3
เพราะฉะนั้น หาค่าลิมิตได้ 3 เป็นค่าคงตัวท่ีไม่เท่ากับ 0 แสดงว่า f(x) = Ѳ(g(x)) คือ f(x) = 3x2 — 2x และ
g(x) = x2 + 5x มีอ ัตราการเติบโตท ี่อ ันดับเดียวกัน
