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

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

n i = n(n + 1)
2
iΣ=1
21 n2 + 21 n
=

และ​จากท​ ฤษฎีบท 2.1 สรุปไ​ด้ว​ ่า 1 + 2 + 3 + … + n = 12 n2 + 21 n = O(n2) นั่นเอง

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

ผลค​ ูณ​ของจ​ �ำนวนเต็ม n ตัวแ​ รก คือ
1 ⋅ 2 ⋅ 3 … ⋅ n = n! คือ ฟังก์ชันแ​ ฟก​ทอเ​รี​ยล (factorial function)

ดังน​ ั้น ทุกๆ พจน์​ใน​การ​คูณ​นี้จ​ ะม​ ีค​ ่าไ​ม่​เกิน n ดังน​ ั้น จะ​ได้ว​ ่า
n! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ n
≤ n ⋅ n ⋅ n ⋅ ... ⋅ n
= nn

นั่นค​ ือ n! เป็น O(nn) โดยท่ี c = 1 และ n0 = 1 เป็นต​ ัวยืน​ยัน​ความส​ ัมพันธ์​น้ี

ตวั อย่าง 2.8 จงห​ า​บิ๊ก​โอ​ของผ​ ล​รวม n 2i
วิธี​ท�ำ
iΣ=1

จากโ​จทย์ต​ ้องการใ​ห้ห​ า​บิ๊ก​โอข​ องฟ​ ังก์ชัน 2 + 22 + 23 + … + 2n
เนื่องจากแ​ ต่ละพ​ จน์​ในฟ​ ังก์ชัน​จะ​มีค​ ่าไ​ม่เ​กิน 2n

ดัง​น้ัน จะ​ได้​ว่า
2 + 22 + 23 + … + 2n ≤ 2n + 2n + 2n + … + 2n = 2n n
n 2i เป็น O(2n n) ท่ี c = 1 และ n0 = 1 เป็นต​ ัวยืน​ยันค​ วาม​สัมพันธ์​น้ี
เพราะ​ฉะนั้น
iΣ=1

กจิ กรรม 2.1.1
1. จง​พิจารณาว​ ่าฟ​ งั กช์ ันต​ อ่ ​ไปน​ เ้ี​ปน็ O(x) หรอื ​ไม่
1.1 f(x) = 100
1.2 f(x) = 3x + 14
1.3 f(x) = 4x2 + 3
2. จง​พิจารณา​วา่ ​ฟังก์ชันต​ ่อ​ไป​นเ​้ี ปน็ O(x2) หรอื ​ไม่
2.1 f(x) = 23x – 19
3. จง​แ22ส..23ด งffว​((xxา่ ))2==x4(xx+24+3x130–)2x2 + 12 เป็น O(x4)
4. จง​แสดง​ว่า 2x + 7 เป็น O(3x)