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

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

แนวต​ อบก​ จิ กรรม 2.1.3
1. จาก​ท​ก่ี ำ�หนดใ​ห้ f(x) = 6x3 – x + 8 และ g(x) = (x2 + 3)(x + 1)
f(x)
จะไ​ดว้​ ่า xl→im∞ g(x) = 6 เป็นค​ า่ ค​ งตวั ท​ ีไ​่ ม่เ​ทา่ กบั 0 แสดง​วา่

f(x) และ g(x) เติบโต​แบบเ​ดยี วกนั ดงั ​น้นั f(x) = Ѳ(g(x))
2. จาก​ท​ก่ี ำ�หนด​ให้ f(n) = (2n + 1)log n และ g(n) = 4n2 + 2n
f(n)
จะ​ไดว​้ ่า nl→im∞ g(n) = 0 แสดง​ว่า f(n) เตบิ โตช​ ้าก​ วา่ g(n) ดงั ​น้นั f(n) = O(g(n))

3. จาก​ทก​ี่ �ำ หนดใ​ห้ f(n) = 5n2 + 2 และ g(n) = 25 + n
f(n)
จะ​ได้ว​ ่า nl→im∞ g(n) = ∞ แสดง​ว่า f(n) เติบโตเ​ร็วก​ ว่า g(n) ดงั ​นัน้ g(n) = O(f(n))

4. จากท​ ก​่ี ำ�หนด​ให้ f(x) = 3x – 1 และ g(x) = 5x3 + 1
f(x)
จะไ​ด้ว​ า่ xl→im∞ g(x) = ∞ แสดงว​ ่า f(x) เตบิ โตเ​ร็วก​ วา่ g(x) ดัง​นนั้ g(x) = O(f(x))

5. จากท​ ​กี่ ำ�หนด​ให้ f(n) = n! และ g(n) = 5n
ใน​ข้อ​นี้ จะ​เห็น​ว่า การ​คำ�นวณ​หา​ค่า​ลิ​มิต​ทำ�ได้​ยุ่ง​ยาก ดัง​น้ัน ให้​พิจารณา​เปรียบ​เทียบ​บิ๊ก​โอ​ของ​แต่ละ​
ฟงั กช์ ัน​แทน จะ​ท�ำ ให้​การพ​ ิจารณา​เปรยี บ​เทียบก​ ารเ​ตบิ โตข​ อง​ฟงั ก์ชันง​ ่าย​และส​ ะดวกย​ ่ิง​ขึน้ ดัง​นัน้ จะ​ไดว​้ ่า
f(n) = n! = O(nn) และ g(n) = 5n = O(5n) ซง่ึ nn ย่อมโ​ตเ​ร็ว​กว่า 5n
เพราะฉ​ ะน้นั f(n) เตบิ โต​เร็วก​ ว่า g(n) ดังน​ ัน้ g(n) = O(f(n))
6. จากท​ ก​่ี ำ�หนดใ​ห้ f(n) = n!log n และ g(n) = n log(n!)
ใน​ข้อ​นี้ จะ​เห็น​ว่า การ​คำ�นวณ​หา​ค่า​ลิ​มิต​ทำ�ได้​ยุ่ง​ยาก ดัง​น้ัน ให้​พิจารณา​เปรียบ​เทียบ​บ๊ิก​โอ​ของ​แต่ละ​
ฟงั ก์ชนั ​แทน จะท​ ำ�ให้ก​ ารพ​ จิ ารณาเ​ปรยี บ​เทียบ​การเ​ตบิ โต​ของฟ​ งั ก์ชนั ง​ ่าย​และส​ ะดวก​ยงิ่ ข​ น้ึ ดัง​นั้น จะ​ได​้ว่า
f(n) = n!log n = O(nnlog n) และ g(n) = n log(n!) = O(n2log n)
เพราะ​ฉะนนั้ f(n) เติบโตเ​รว็ ​กว่า g(n) ดงั น​ ้ัน g(n) = O(f(n))
7. ให้​บอกส​ ญั ลกั ษณ​บ์ ๊กิ ​โอ​ของ​ฟงั กช์ นั พรอ้ ม​ทัง้ ร​ ะบ​วุ ่า​ฟังก์ชนั ​ไหนโ​ต​เรว็ ​กว่า​กัน
7.1 ฟงั ก์ชนั ค​ ่าค​ งตัว เปน็ O(1)
ฟังกช์ นั ล​ อก​าร​ ิธมึ เปน็ O(log x)
ดงั น​ ั้น ฟงั กช์ นั ล​ อกา​ ร​ ธิ มึ ​โต​เรว็ ก​ ว่าฟ​ ังกช์ ันค​ ่าค​ งตัว
7.2 ฟังกช์ นั เ​ชิงเ​สน้ เป็น O(x)
ฟังก์ชนั ล​ อกา​ ร​ ธิ มึ เปน็ O(log x)
ดังน​ นั้ ฟังกช์ ัน​เชิงเ​สน้ โ​ตเ​รว็ ​กวา่ ​ฟงั ก์ชนั ​ลอกา​ ​ริธึม
7.3 ฟังกช์ ัน​ลอ็ ก​ส​แควร​ ์ เปน็ O(log2 x)
ฟังก์ชนั ​กำ�ลัง​สอง เปน็ O(x2)
ดัง​นนั้ ฟงั กช์ ัน​กำ�ลงั ส​ องโ​ตเ​ร็วก​ ว่า​ฟงั ก์ชนั ล​ อ็ กส​ แ​ ควร​ ์
7.4 ฟังกช์ ัน​ลอกา​ ร​ ิธมึ เป็น O(log x)
ฟังก์ชนั เ​อ็กซ์​โพเนนเ​ชยี ​ล เป็น O(ex)
ดังน​ นั้ ฟังก์ชนั เ​อก็ ซ์โ​พเนนเ​ชยี ​ลโ​ตเ​ร็ว​กว่า​ฟงั กช์ ัน​ลอก​า​รธิ ึม