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

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

ทฤษฎีบท 2.2 กำ�หนดใ​ห้ f1(x) = O(g1(x)) และ f2(x) = O(g2(x)) แล้ว (f1+ f2)(x) = O(max(|g1(x)|,|g2(x)|))

ขอ้ ​สังเกต จาก​ทฤษฎีบท​นี้ ถ้าก​ ารป​ ระม​ าณ​บิ๊ก​โอ​ของ f1 และ f2 ได้เ​ป็น​ฟังก์ชันเ​ดียวกัน คือ g(x)
จะ​ได้​ว่า (f1 + f2)(x) เป็น O(g(x)) ด้วย เพราะว​ ่า max(|g(x)| , |g(x)|) = g(x)

ตวั อยา่ ง​ท่ี 2.9 จงห​ าบ​ ๊ิก​โอข​ องฟ​ ังก์ชัน g(x) = 4x + log x
วิธ​ที �ำ

พิจารณาฟ​ ังก์ชัน g(x) จะไ​ด้​ว่า g(x) เป็นการ​บวกก​ ัน​ของ​ฟังก์ชัน 4x กับ log x
โดย​พิจารณาบ​ ิ๊ก​โอข​ อง​ทั้ง​สองฟ​ ังก์ชัน จะ​ได้ว​ ่า 4x = O(x) และ log x = O(log x)
ดังน​ ้ัน จากท​ ฤษฎีบท 2.2 จะไ​ด้​ว่า g(x) = O(max(|x|, |log x|)) = O(x) นั่นเอง

2. การ​คณู ก​ ัน​ของฟ​ งั กช์ ัน

ในท​ �ำนองเ​ดียวกัน การป​ ระม​ าณบ​ ิ๊กโ​อส​ �ำหรับก​ ารค​ ูณก​ ันข​ องฟ​ ังก์ชัน 2 ฟังก์ชัน สามารถก​ ระท�ำไ​ด้เ​ช่นเ​ดียวกัน
โดย​สรุป​เป็นท​ ฤษฎีบท​ได้ ดังนี้

ทฤษฎบี ท 2.3 กำ�หนดใ​ห้ f1(x) = O(g1(x)) และ f2(x) = O(g2(x)) แล้ว (f1⋅f2)(x) = O(g1(x)⋅g2(x))

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

ดังน้ี พิจารณา (x + 1) log(x2 + 1) ซึ่งเ​ป็นการ​คูณก​ ันร​ ะหว่าง (x + 1) กับ log(x2 + 1)

ดังน​ ั้น หา​บิ๊ก​โอ​ส�ำหรับ (x + 1) จะไ​ด้ (x + 1) = O(x) ...............(1)
และห​ า​บิ๊กโ​อส​ �ำหรับ log(x2 + 1)
ซึ่งพ​ ิจารณา​แล้ว จะ​เห็น​ว่า x2 + 1 ≤ 2x2 เมื่อ x > 1
ดังน​ ้ัน log(x2 + 1) ≤ log(2x2)
≤ log 2 + log x2

≤ log 2 + 2 log x

≤ 3 log x ถ้า x > 2
น่ัน​คือ log(x2 + 1) = O(log x)
ดัง​น้ัน จาก (1) และ (2) จะไ​ด้​ว่า (x + 1) log(x2 + 1) = O(x log x) ทฤษฎีบท 2.3 ...............(2)

พิจารณา 3x2 จะไ​ด้​ว่า 3x2 = O(x2) ...............(3)

...............(4)
เพราะ​ฉะน้ัน จาก (3) และ (4) จะ​ได้​ว่า f(x) = (x + 1) log(x2 + 1) + 3x2 = O(max(x log x, x2)) = O(x2)

โดยอ​ าศัยท​ ฤษฎีบท 2.2