Page 12 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 12
2-2 โครงสร้างข้อมูลและขั้นตอนวิธี
แผนการสอนประจ�ำ ห น่วย
ชุดว ิชา โครงสร้างข ้อมูลแ ละขั้นต อนวิธี
หน่วยท ี่ 2 การวัดป ระสิทธิภาพและความซ ับซ้อนข องข้ันต อนวิธี
ตอนท่ี
2.1 การเติบโตข องฟ ังก์ชัน
2.2 การวิเคราะห์ขั้นตอนวิธี
แนวคิด
1. ป ระสิทธิภาพของขั้นตอนวิธีสามารถวัดได้จากการหาอัตราการเติบโตของฟังก์ชันเวลาท่ีใช้ประมวลผล
ขอ้ มูล ขอบเขตก ารเติบโตของฟ งั ก์ชันส ามารถอธิบายได้ด ว้ ยส ญั ลักษณบ์ ิ๊กโอ บก๊ิ โอเมก าและบิ๊กท ีตา โดย
บิ๊กโอใช้อธิบายขอบเขตบน บ๊ิกโอเมกาใช้อธิบายขอบเขตล่าง และบิ๊กทีตาใช้อธิบายท้ังขอบเขตบนและ
ล่างข องการเติบโตของฟังก์ชัน
2. ก ารวิเคราะห์ประสิทธิภาพของขั้นตอนวิธีเป็นการศึกษารูปแบบการเขียนโปรแกรมและล�ำดับข้ันตอน
การท �ำงานต่างๆ ทั้งก ารเขียนเง่ือนไข การวนท�ำซ �้ำ และการค �ำนวณ
วตั ถุประสงค์
เม่ือศ ึกษาหน่วยท ่ี 2 จบแล้ว นักศึกษาสามารถ
1. เปรียบเทียบการเติบโตของฟ ังก์ชันต ่างๆ ได้
2. หาส ัญญาก รณ์บ ิ๊กโอในการอ ธิบายประสิทธิภาพของข้ันตอนวิธีได้
3. เปรียบเทียบป ระสิทธิภาพของข ั้นต อนวิธีต ่างๆ ได้
กิจกรรมระหวา่ งเรียน
1. ท�ำแ บบประเมินผลต นเองก ่อนเรียนหน่วยท่ี 2
2. ศึกษาเอกสารการส อนต อนท ี่ 2.1-2.2
3. ปฏิบัติก ิจกรรมตามท่ีได้รับม อบห มายในเอกสารการส อนแต่ละเร่ือง
4. ศึกษาสื่อการสอนอิเล็กทรอนิกส์ป ระจ�ำช ุดว ิชา
5. ฟังร ายการว ิทยุก ระจายเสียง (ถ้ามี)
6. ชมรายการวิทยุโทรทัศน์ (ถ้ามี)
7. ชมรายการสอนเสริมผ่านส่ืออิเล็กทรอนิกส์ (e-Tutorial)
8. ท�ำแ บบป ระเมินผ ลตนเองหลังเรียนห น่วยที่ 2
9. ท�ำก ิจกรรมป ระจ�ำช ุดว ิชา (ถ้ามี)
