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

การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-17

ตัวอยา่ ง​ท่ี 2.11 จงห​ าบ​ ิ๊ก​โอ​ของ​ฟังก์ชัน f(n) = 3n log(n!) + (n2 + 3)log n โดยท่ี n เป็น​จ�ำนวนเต็มบ​ วก
วิธี​ท�ำ
เน่ืองจาก f(n) เป็นการ​บวก​กัน​ระหว่าง 3n log(n!) กับ (n2 + 3)log n สามารถ​แยก​การ​พิจารณา​แต่ละ​พจน์​

ได้ดังน้ี

พิจารณา 3n log(n!) ซ่ึงเ​ป็นการค​ ูณ​กันร​ ะหว่าง 3n กับ log(n!)

ดัง​น้ัน

หาบ​ ิ๊กโ​อส​ �ำหรับ 3n จากท​ ฤษฎีบท 2.1 ฟังก์ชันพ​ หุน​ าม จะ​ได้ ว่า 3n = O(n) ...............(1)
หา​บิ๊ก​โอส​ �ำหรับ log(n!) เนื่องจาก n! = O(nn)
น่ันค​ ือ n! ≤ nn
โดยก​ ารใ​ช้ล​ อก​าร​ ิธึม (logarithm) ทั้งเม​สื่อองcข​ ้า=งข​1อแงล​สะมกn0าร>จ1ะไ​ด้
log(n!) ≤ log nn

≤ n log n

ดังน​ ั้น log(n!) = O(n log n) ...............(2)
ซึ่ง​จาก (1) และ (2) จะ​ได้ 3n log(n!) = O(n2 log n) โดยท​ ฤษฎีบท 2.3
พิจารณา (n2 + 3)log n ซึ่งเ​ป็นการค​ ูณก​ ันร​ ะหว่าง (n2 + 3) กับ log n ...............(3)

ดังน​ ั้นหา​บ๊ิก​โอ​ส�ำหรับ (n2 + 3) จากท​ ฤษฎีบท 2.1 ฟังก์ชันพ​ หุ​นาม จะ​ได้ ว่า (n2 + 3) = O(n2)

และ​จาก​ทฤษฎีบท 2.3 จะ​ได้​ว่า (n2 + 3)log n = O(n2 log n) ...............(4)

เพราะ​ฉะนั้น จาก (3) และ (4) จะ​ได้
f(n) = 3n log(n!) + (n2 + 3)log n เป็น O(n2 log n) ทฤษฎีบท 2.2

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

ทฤษฎบี ท 2.4 กำ�หนดใ​ห้ fi(x) = O(gi(x)) เมื่อ i = 1, 2, …, n
แล้ว (f1 + f2 + … + fn)(x) = O(max(|g1(x)| , |g2(x)| ,…, |gn(x)|))

ทฤษฎบี ท 2.5 แกลำ�ห้วน(ดf1​ใ⋅หf2้ ⋅f…i(x⋅)f=n)(Ox)(g=i(xO))(gเ1ม(ื่อx)⋅ig=2(1x,) 2, …, n
⋅…⋅ gn(x))

ตวั อยา่ ง​ที่ 2.12 จง​หาบ​ กิ๊ ​โอข​ อง​ฟงั กช์ นั f(n) = (n + 2)n4log n + 4n log(n2) + (n5 + 3) โดยที่ n เปน็ ​จ�ำนวนเตม็ บ​ วก
วิธ​ีท�ำ

เน่ืองจาก f(n) เป็นการบ​ วก​กัน​ของ (n + 2)n4log n และ 4n log(n2) และ (n5 + 3)
สามารถแ​ ยกก​ าร​พิจารณาแ​ ต่ละพ​ จน์​ได้ ดังต​ ่อไ​ปน​ ้ี
พิจารณา (n + 2)n4log n ซ่ึงเ​ป็นการ​คูณก​ ัน​ของ (n + 2) และ n4 และ log n