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

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

ตัวอยา่ งท​ ี่ 2.15 จงเ​รียงล​ �ำดับ​อัตราก​ าร​เติบโต​ของ​ฟังก์ชัน​ต่อ​ไป​นี้​จากช​ ้า​ไปเ​ร็ว
5n n 45 log n
วธิ ท​ี �ำ
พิจารณาแ​ ต่ละฟ​ ังก์ชัน จะเ​ห็นว​ ่า 45 เป็นค​ ่าค​ งตัว แสดงว​ ่าเ​ป็นฟ​ ังก์ชันค​ ่าค​ งตัว ซึ่งม​ ีอ​ ัตราก​ ารเ​ติบโตเ​ป็นศ​ ูนย์

จะ​เติบโต​ช้า​ที่สุด ส่วน n และ log n ย่อม​โต​ช้า​กว่า 5n ดัง​น้ัน เหลือ​การ​พิจารณา​เปรียบ​เทียบ​ว่า n กับ

log n ฟังก์ชัน​ไหนโ​ตเ​ร็วกว​ ่า​กัน
ซึ่ง n มี​ค่า​เท่ากับ n0.5 จึง​เปรียบ​เทียบ n0.5 กับ log n จะ​เห็น​ว่า​ทั้ง​สอง​ฟังก์ชัน​มี​ค่า​มากกว่า​ศูนย์ ดัง​นั้น

เม่ือย​ ก​ก�ำลัง​สองท​ ั้ง​สองฟ​ ังก์ชัน ความส​ ัมพันธ์​ระหว่างท​ ้ัง​สองฟ​ ังก์ชัน​ไม่เ​ปล่ียนแปลง นั่น​คือ มา​พิจารณา​เปรียบ​เทียบ
n กับ log2 n แทน แล้วพ​ บว่า n โตเ​ร็วก​ ว่า log2 n ดัง​นั้น n0.5 จึง​โต​เร็ว​กว่า log n น่ันเอง (เช่นเ​ดียวก​ ับ​ท่ีก​ ล่าวมาแ​ ล้ว​

ก่อน​หน้าน​ ้ี)

เพราะฉ​ ะนั้น​เรียงล​ �ำดับอ​ ัตราก​ ารเ​ติบโต​ของ​ฟังก์ชัน​จาก​ช้าไ​ป​เร็วไ​ด้ด​ ังนี้

ข้อ​สังเกต ถ้าป​ ระมาณ​เป็น​บ๊ิกโ​อ​จะ​ได้ว​ ่า 45 log n n 5n

5n เป็น O(n) 45 เป็น O(1)

n เป็น O( n ) log n เป็น O(log n)

กจิ กรรม 2.1.3
1. ก�ำ หนดใ​ห้ f(x) = 6x3 – x + 8 และ g(x) = (x2 + 3)(x + 1) จง​หาว​ ่าฟ​ ังกช์ นั ​ไหน​โตเ​รว็ ​กว่า​กัน
2. ก�ำ หนด​ให้ f(n) = (2n + 1)log n และ g(n) = 4n2 + 2n จง​หาว​ า่ ​ฟงั ก์ชนั ไ​หนโ​ตเ​ร็ว​กว่าก​ ัน
3. กำ�หนดใ​ห้ f(n) = 5n2 + 2 และ g(n) = 25 + n จง​หา​วา่ ฟ​ ังกช์ ัน​ไหน​โตเ​รว็ ก​ วา่ ​กนั
4. กำ�หนดใ​ห้ f(x) = 3x – 1 และ g(x) = 5x3 + 1 จงห​ าว​ า่ ​ฟงั กช์ ัน​ไหนโ​ตเ​ร็ว​กว่าก​ ัน
5. กำ�หนดใ​ห้ f(n) = n! และ g(n) = 5n จงห​ า​ว่าฟ​ ังก์ชัน​ไหนโ​ตเ​ร็ว​กวา่ ​กนั
6. กำ�หนดใ​ห้ f(n) = n!log n และ g(n) = n log(n!) จง​หาว​ า่ ฟ​ ังก์ชัน​ไหนโ​ตเ​รว็ ก​ วา่ ​กนั
7. จงบ​ อก​สญั ลักษณ์บ​ ิก๊ ​โอ​ของ​ฟงั ก์ชันต​ อ่ ไ​ป​นี้ พร้อม​ทั้ง​ระบุ​วา่ ​ฟงั กช์ ันไ​หนโ​ตเ​ร็ว​กว่า​กัน
7.1 ฟงั กช์ ันค​ ่าค​ งตวั กบั ฟังกช์ นั ​ลอการธิ มึ
7.2 ฟังก์ชัน​เชิง​เสน้ กบั ฟงั กช์ นั ล​ อก​า​ริธมึ
7.3 ฟงั ก์ชัน​ลอ็ ก​ส​แคว​ร์ กบั ฟงั ก์ชันก​ �ำ ลงั ​สอง
7.4 ฟังก์ชนั ล​ อก​าร​ ิธมึ กบั ฟังกช์ นั เ​อ็กซโ​์ พเนนเ​ชีย​ล
7.5 ฟงั ก์ชันก​ ำ�ลัง​สิบ กบั ฟังก์ชนั เ​อ็กซโ​์ พเนนเ​ชียล​
8. จงเ​รยี ง​ล�ำ ดับ​อตั รา​การ​เติบโต​ของ​ฟงั กช์ ันต​ อ่ ​ไปน​ ​ี้จาก​ช้าไ​ปเ​ร็ว
n n2 + log n log n n! 3n
9. จงเ​รยี ง​ลำ�ดับ​อตั รา​การเ​ติบโต​ของฟ​ ังกช์ นั ​ตอ่ ไ​ป​นี้​จาก​เรว็ ​ไปช​ า้
n2 n! log n 26 n log n 4n5