Page 14 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 14
2-4 โครงสร้างข้อมูลและขั้นตอนวิธี
ตอนท ่ี 2.1
การเตบิ โตข องฟังกช์ นั
โปรดอ ่านหัวเรื่อง แนวคิด และว ัตถุประสงค์ของตอนที่ 2.1 แล้วจึงศึกษาร ายละเอียดต่อไป
หัวเรื่อง
2.1.1 ความห มายข อง บิ๊กโอ บิ๊กโอเมก า และบ๊ิกทีตา
2.1.2 การเติบโตข องก ารรวมกันข องฟังก์ชัน
2.1.3 การเปรียบเทียบการเติบโตของฟ ังก์ชัน
แนวคิด
1. ประสทิ ธภิ าพของขนั้ ตอนวธิ สี ามารถวดั ไดจ้ ากการหาอตั ราการเตบิ โตของฟงั กช์ นั เวลาทใ่ี ชป้ ระมวลผล
ข้อมูล ขอบเขตการเติบโตของฟังก์ชันสามารถอธิบายได้ด้วยสัญลักษณ์บิ๊กโอ บิ๊กโอเมกาและ
บ๊ิกทีตา โดยบิ๊กโอใช้อธิบายขอบเขตบน บ๊ิกโอเมกาใช้อธิบายขอบเขตล่าง และบ๊ิกทีตาใช้อธิบาย
ทั้งขอบเขตบนและล่างของการเติบโตของฟังก์ชัน
2. การหาการเติบโตของฟังก์ชันด้วยบ๊ิกโอของฟังก์ชันท่ีเกิดจากการรวมกันของฟังก์ชันต้ังแต่ 2
ฟังก์ชัน ขึ้นไป ท�ำได้โดยการแยกหาบ๊ิกโอของแต่ละฟังก์ชันก่อน แล้วน�ำบ ๊ิกโอที่ได้มาพิจารณา
ร่วมกัน ซึ่งอ าจเป็นได้ท ั้งก ารบ วกฟ ังก์ชันท ้ังส องเข้าด ้วยก ัน หรือก ารค ูณฟ ังก์ชันท ้ังส องเข้าด ้วยกัน
3. ก ารเปรียบเทียบการเติบโตของฟังก์ชัน สามารถท�ำได้โดยการหาค่าลิมิต แต่การประมาณฟังก์ชัน
ด้วยบิ๊กโอก่อนแล้วเปรียบเทียบจะท�ำได้รวดเร็วและง่ายกว่า อีกทั้งยังสอดคล้องกับการพิจารณา
ประสิทธิภาพของข ้ันต อนว ิธี
วัตถุประสงค์
เม่ือศ ึกษาตอนท ่ี 2.1 จบแ ล้ว นักศึกษาส ามารถ
1. ค�ำนวณห าบ ิ๊กโอของฟังก์ชันท ี่ก�ำหนดให้ได้
2. ค�ำนวณห าบ๊ิกโอข องฟังก์ชันท ี่เกิดจากการรวมก ันข องห ลายฟ ังก์ชันได้
3. บอกค วามแตกต ่างของบิ๊กโอ บ๊ิกโอเมกา และบ ๊ิกทีต าได้
4. เปรียบเทียบก ารเติบโตของฟังก์ชันได้
