Page 57 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 57
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-47
ถ้าประมวลผ ลข ้อมูล 5,000 ข้อมูล จะใช้เวลา 5000 × 12 = 600 วนิ าที
100
เพราะฉ ะนนั้ ขัน้ ต อนว ิธนี จ้ี ะใชเ้ วลา 600 วินาที ในก ารป ระมวลผ ลข ้อมูลท ัง้ หมด 5,000 ขอ้ มูล
2.3 ถ้าฟังก์ชันเวลา T(n) ของข้ันตอนวิธีน้ี มีอัตราการเติบโตเป็น O(log n) แสดงว ่า ขั้นตอน
ว ธิ นี ี้ ใชเ้ วลาในก ารป ระมวลผ ลข อ้ มลู 100 ขอ้ มลู ทแ่ี ปรผนั ต รงก บั ข นาดข อ้ มลู ในส ดั สว่ น log(100) เปน็ 12 วนิ าที
ถ้าป ระมวลผ ลข ้อมลู 5,000 ข้อมลู ทแี่ ปรผนั ต รงก ับข นาดข อ้ มลู ในส ดั ส่วน log(5000) จะใชเ้วลา
log(5000) × 12 = log(5 × 103) × 12
log(100) log(102)
= log(5) + log(103) × 12
log(102)
= log(5) + 3log(10) × 12
2log(10)
= log(5) + 3 × 12
2
= 6 log(5) + 18
เพราะฉ ะนน้ั ขน้ั ต อนว ธิ นี ใี้ ชเ้ วลา6log(5) +18วนิ าที ในก ารป ระมวลผ ลข อ้ มลู ท งั้ หมด5,000ขอ้ มลู
2.4 ถา้ ฟังก์ชันเวลา T(n) ของข น้ั ตอนวธิ ีน้ี มอี ัตราก ารเตบิ โตเป็น O(n3) แสดงว า่ ขนั้ ต อนวธิ ีน้ี
ใชเ้ วลาในก ารประมวลผ ลขอ้ มูล 100 ข้อมูลทแ่ี ปรผนั ต รงกบั ขนาดข อ้ มูลในส ดั สว่ น 1003 เปน็ 12 วนิ าที
ถ้าประมวลผลข้อมูล 5,000 ข้อมูลท่ีแปรผันตรงกับขนาดข้อมูลในสัดส่วน 50003 จะใช้เวลา
50003 × 12 = 1,500,000 วินาที
1002 เพราะฉ ะนน้ั ขน้ั ต อนว ธิ นี ใ้ี ชเ้ วลา 1,500,000 วนิ าที ในการป ระมวลผ ลข อ้ มลู ท ง้ั หมด 5,000 ขอ้ มลู
