Page 30 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 30
2-20 โครงสร้างข้อมูลและขั้นตอนวิธี
การค�ำนวณหาค่าลิมิตมีความยุ่งยากและซับซ้อน ซ่ึงบ่อยครั้งไม่จ�ำเป็นต้องหาค่าลิมิตที่ชัดเจน อาจต้องการ
ทราบเพียงว ่าฟ ังก์ชันไหนโตเร็วก ว่ากัน ดังแ สดงในภาพท ี่ 2.4
100f(x) x3 x2
80
60 x log x
40 5 10 x
log2x
20 loxg x
15 20
0
0
ภาพท่ี 2.4 กราฟแ สดงการเตบิ โตของฟ งั กช์ ันพื้นฐานตา่ งๆ
อีกวิธีหน่ึงที่สามารถหาความสัมพันธ์ระหว่าง f(x) กับ g(x) ได้ คือ การแปลงทางพีชคณิตและการพิจารณา
เทียบเคียงก ับรูปแ บบก ารเติบโตของฟ ังก์ชันท ี่รู้อยู่ก ่อนแล้วว ่าฟ ังก์ชันไหนโตเร็วกว่าฟังก์ชันไหนได้
เช่น ถ้า f(x) = x log x และ g(x) = x1.5 ฟังก์ชันไหนโตเร็วกว่าก ัน
ให้พิจารณาตัดทอน x ด้วยการหารทั้งสองฟังก์ชันด้วย x เม่ือ x มีค่าเป็นบวกได้ และความสัมพันธ์ของสอง
ฟังก์ชันยังค งเหมือนเดิม ท�ำให้เหลือการพิจารณาเพียงค่าระหว่าง log x กับ x0.5
จากน ั้นพ ิจารณาค ่ายกก�ำลังส องข องท้ังส องฟังก์ชัน จะได้เป็น log2 x กับ x
ซ่ึงทราบว่า ฟังก์ชัน x โตเร็วก ว่า log x และโตเร็วก ว่าค่า log x ท่ียกก�ำลังสองด้วย (น่ันค ือ เม่ือ x มีค่าม ากๆ
เช่น เม่ือ x > 102 จะได้ log2 x < x เสมอ)
ดังน ้ัน g(x) จึงโตเร็วกว่า f(x) ซ่ึงห มายความว่า x1.5 โตเร็วก ว่า x log x นั่นเอง
ในตารางที่ 2.2 แสดงชื่อรูปแบบฟังก์ชันพื้นฐานต่างๆ ท่ีเรียงล�ำดับอัตราการเติบโตของฟังก์ชันจากช้าไปถึง
เร็ว และในภาพที่ 2.4 แสดงกราฟการเตบิ โตของฟงั กช์ นั พน้ื ฐานตา่ งๆ เหลา่ นี้ (ยกเวน้ ฟงั กช์ นั คา่ คงตวั กบั เอก็ ซโ์ พเนนเชยี
ล) จะสังเกตได้ว่าเมื่อพิจารณาฟังก์ชันเวลา T(n) ที่ใช้ในการประมวลผลของขั้นตอนว ิธีหน่ึงๆ ถ้าฟังก์ชันน้ีมีอ ัตราการ
เติบโตชา้ แสดงวา่ เมอ่ื มขี อ้ มลู มาก ขนั้ ตอนวธิ นี ยี้ งั คงท�ำงานไดเ้ รว็ แตถ่ า้ ฟงั กช์ นั เวลานม้ี อี ตั ราการเตบิ โตเรว็ หมายความวา่
เมื่อมีข้อมูลมาก เวลาที่ใช้ประมวลก็เติบโตตามขนาดของข้อมูลและอาจประมวลผลได้ช้า ท�ำให้เป็นข้ันตอนวิธีที่ไม่มี
ประสิทธิภาพน่ันเอง เช่น ถ้าขั้นตอนวิธีหนึ่งใช้เวลาเป็น O(log n) และอ ีกขั้นต อนว ิธีห นึ่งใช้เวลาเป็น O(2n) เพื่อป ระมวล
ข้อมูลให้ได้ผลเช่นเดียวกัน สมมติว่า n = 10 จะเห็นว่าข้ันตอนวิธีแรกจะใช้เวลาประมาณ log 10 ซ่ึงเท่ากับ 1 หน่วย
เวลาในก ารประมวลผ ล แต่ข ้ันต อนวิธีที่สอง จะใช้เวลาถึง 210 หน่วยเวลา ซ่ึงช ้ามาก ดังน้ัน ข้ันต อนว ิธีแรกจึงท�ำงาน
ได้ดีมีประสิทธิภาพม ากกว่าขั้นตอนวิธีท่ีส อง ท่ีใช้เวลาเป็นเอ็กซ์โพเนนเชียล
