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

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

ดัง​นั้น

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

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

ดังน​ ้ัน

หาบ​ ิ๊ก​โอ​ส�ำหรับ 4n จาก​ทฤษฎีบท 2.1 ฟังก์ชันพ​ หุน​ าม จะ​ได้ว​ ่า 4n = O(n) ................(5)
หาบ​ ิ๊กโ​อส​ �ำหรับ log(n2) ซ่ึง log(n2) = 2 log n จะไ​ด้ว​ ่า log(n2) = O(log n) ................(6)
ซึ่งจ​ าก (5) และ (6) จะ​ได้​ว่า 4n log(n2) = O(n log n) ................(7)
พิจารณา (n5 + 3) จากท​ ฤษฎีบท 2.1 ฟังก์ชันพ​ หุ​นาม จะ​ได้ว​ ่า (n5 + 3) = O(n5)
................(8)

เพราะฉ​ ะนั้น จาก (4) (7) และ (8) โดย​อาศัย​ทฤษฎีบท 2.2
จะ​ได้ f(n) = (n + 2)n4log n + 4n log(n2) + (n5 + 3) เป็น O(max(n5log n, log n, n5))
น่ันค​ ือ f(n) = O(n5log n)

กจิ กรรม 2.1.2
1. จงห​ า​บ๊กิ โ​อส​ ำ�หรับฟ​ งั ก์ชนั 14x3 + (x2 –1)(x + 1)
2. จงห​ า​บก๊ิ ​โอส​ ำ�หรบั ฟ​ ังก์ชัน n2log n + (n2 + 1)
3. จง​หา​บกิ๊ โ​อ​สำ�หรบั ​ฟังกช์ ัน (2n + n2)(n3 + 3n)
4. จง​หาบ​ ๊ิก​โอ​สำ�หรับ​ฟังกช์ นั n log(n2 + 1) + n2 log n
5. จง​หา​บกิ๊ โ​อ​สำ�หรับฟ​ งั ก์ชัน 3n2 log(n2 + 2n) + log n5 + n3 log(8n)

แนวต​ อบ​กิจกรรม 2.1.2
1. บกิ๊ ​โอส​ ำ�หรับ​ฟงั กช์ ัน 14x3 + (x2 – 1)(x + 1) = O(x3)
2. บ๊ิกโ​อ​ส�ำ หรับ​ฟังกช์ นั n2log n + (n2 + 1) = O(n2log n)
3. บก๊ิ โ​อ​ส�ำ หรับ​ฟังกช์ ัน (2n + n2)(n3 + 3n) = O(n2 ⋅ 3n)
4. บก๊ิ โ​อส​ ำ�หรบั ​ฟังกช์ นั n log(n2 + 1) + n2 log n = O(n2log n)
5. บ๊ิก​โอ​ส�ำ หรบั ฟ​ ังกช์ ัน 3n2 log(n2 + 2n) + log n5 + n3 log(8n) = O(n3log n)