Page 22 - โครงสร้างข้อมูลและขั้นตอนวิธี

2-12 โครงสร้างข้อมูลและขั้นตอนวิธี

ดังน​ ้ัน f(x) = o(x6)
สังเกตว​ ่า cx4 < 4x5 ส�ำหรับท​ ุกๆ
จะ​ได้​ว่า cx4 < f(x) เมื่อ ค่าค​ งตัว​บวก c และเ​ม่ือ x0 = 0 จากบ​ ท​นิยามล​ ิตเ​ทิล​โอ​เม​กา
ดังน​ ั้น f(x) = ω(x4)
x > x0

5. การเ​ตบิ โต​ของฟ​ งั กช์ ัน​พห​ุนาม

ทฤษฎีบท 2.1 การ​เติบโต​ของ​ฟังก์ชัน​พหุน​ าม f(x) = anxn + an—­ 1xn—­ 1 + … + a1x + a0 ที่ a0, a1, …, an—1, an เป็น​
จำ�นวน​จริงใ​ดๆ แล้ว f(x) = O(xn)

จาก​ทฤษฎีบทน​ ้ี จะไ​ด้ว​ ่า ฟังก์ชัน​พหุน​ าม​ใดๆ สามารถ​หาบ​ ิ๊กโ​อ​เพื่ออ​ ธิบายข​ อบเขต​บนข​ อง​ฟังก์ชันไ​ด้​อย่างง​ ่าย​
และ​รวดเร็วข​ ้ึน ดังจ​ ะ​เห็น​ได้จ​ ากต​ ัวอย่าง​ต่อไ​ป​น้ี

ตัวอยา่ งท​ ่ี 2.5 จงห​ า​บิ๊กโ​อข​ อง​ฟังก์ชัน​ต่อ​ไปน​ ้ี
1) f(x) = 3x4 + 2x2 + x ­—­ 3
2) g(x) = 2x + x — 3x6

วธิ ​ที �ำ
1) f(x) = 3x4 + 2x2 + x — 3
จากท​ ฤษฎีบท 2.1 จะ​ได้ว​ ่า f(x) เป็น O(x4)
2) g(x) = 2x + x — 3x6
สามารถ​จัดร​ ูปใ​หม่​เพ่ือ​ให้​เข้าใจง​ ่ายไ​ด้ จะไ​ด้
g(x) = 2x + x — 3x6 = —3x6 + 3x
จากท​ ฤษฎีบท 2.1 จะ​ได้​ว่า g(x) เป็น O(x6)

ตัวอยา่ งท​ ี่ 2.6 จงห​ าบ​ ๊ิกโ​อข​ องผ​ ล​บวกข​ อง​จ�ำนวนเต็มบ​ วก n จ�ำนวน​แรก
วิธ​ีท�ำ

จากโ​จทย์ต​ ้องการใ​ห้ห​ า​บิ๊ก​โอ​ของผ​ ล​บวก n จ�ำนวน​แรก ซ่ึงห​ มายถ​ ึง​ฟังก์ชัน f(x) = 1 + 2 + 3 + … + n
จาก​บท​นิย​ ามบ​ ิ๊กโ​อ ต้องหาต​ ัวยืนย​ ัน c และ n0 เพ่ือป​ ระม​ าณ​บ๊ิก​โอข​ องฟ​ ังก์ชัน​นี้ ซึ่งส​ ามารถ​พิจารณาไ​ด้ ดังนี้
เน่ืองจากแ​ ต่ละ​พจน์​ของ​จ�ำนวนเต็มใ​นฟ​ ังก์ชันจ​ ะ​มีค​ ่าไ​ม่​เกิน n ให้ n0 = 1 แล้ว n > n0
ดังน​ ้ัน จะไ​ด้​ว่า

1 + 2 + 3 + … + n ≤ n + n + n + … + n = n2
เพราะฉ​ ะน้ัน 1 + 2 + 3 + … + n เป็น O(n2) ท่ี c = 1 และ n0 = 1 เป็นต​ ัวยืนย​ ันค​ วาม​สัมพันธ์​นี้

จากต​ ัวอย่างท​ ี่ 2.6 สามารถป​ ระม​ าณบ​ ิ๊กโ​อข​ อง​ผลบ​ วกข​ อง​จ�ำนวนเต็ม n จ�ำนวน​แรก​ได้อ​ ีก​วิธีห​ น่ึง​ โดยอ​ าศัย​

ทฤษฎีบท 2.1 ท่ี​เกี่ยว​กับฟ​ ังก์ชันพ​ หุน​ าม​ข้าง​ต้นแ​ ละค​ วาม​รู้​เร่ืองอ​ นุกรม​ได้ ดังนี้
n
ผล​รวม​ของ​จ�ำนวนเต็ม n ตัว​แรก คือ 1 + 2 + 3 + … + n = i จาก​ความ​รู้​เร่ือง​อนุกรม​ผล​รวม​นี้​จะ​มี​ค่า​
n(n + 1) iΣ=1
เท่ากับ 2 ดังน​ ้ัน จะ​ได้ว​ ่า