Page 55 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 55
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-45
ข้นั ต อนว ธิ ีที่ 3 มีป ระสิทธิภาพเป็น O(n log n)
ใช้การด�ำเนินก ารหรือเวลาท ั้งหมดป ระมาณ 1000 log(1000) = 3 × 103 หน่วยเวลา
ขัน้ ต อนวิธที ่ี 4 มีป ระสิทธิภาพเป็น O(n)
ใช้ก ารด �ำเนินก ารหรือเวลาท้ังหมดป ระมาณ 1000 = 103 หน่วยเวลา
หมายเหต:ุ หน่วยเวลาในที่นี้ หมายถึง จำ�นวนตัวดำ�เนินการด้วย ดังนั้น ถ้าใช้เวลาเป็น 10 หน่วยเวลา จึงหมายความว่า
ใช้ต ัวดำ�เนินก ารทั้งหมด 10 ตัวดำ�เนินก ารในการป ระมวลผล
ตัวอย่างท่ี 2.22 ข้ันตอนวิธีหน่ึงใช้เวลา 10 วินาที ในการประมวลผลข้อมูลท้ังหมด 25 ข้อมูล จงหาว่าขั้นตอนวิธีนี้
จะใช้เวลากี่วินาทีในการประมวลผลข ้อมูลขนาด 4,000 ข้อมูล ถ้าฟังก์ชันเวลา T(n) ที่ขึ้นอยู่กับข นาดของข้อมูล n ของ
ขั้นตอนว ิธีน ี้มีอ ัตราก ารเติบโตเป็นเชิงเส้น
วิธีท�ำ
ถ้าฟ ังก์ชันเวลา T(n) ของข ั้นตอนว ิธีนี้ มีอัตราก ารเติบโตเป็นเชิงเส้นห มายความว ่าเป็น O(n)
แสดงว ่า
ข้ันตอนว ิธีน ี้ ใช้เวลาในการป ระมวลผ ลข้อมูล 25 ข้อมูลท ่ีแปรผันต รงกับขนาดข ้อมูลเป็น 10 วินาที
เถพ้ารป าระะฉมะวนลั้นผ ลข้ันข ้อตมอูลนว4ิธ,0ีน0้ีใ0ช้เขว้อลมาูล1ท,6ี่แ0ป0รวผินันาตทรี ใงนก กับาขรนป ารดะขม้อวมลูลผ จละขใ้อชม้เวูลลทาั้งห420ม.05ด0
× 10 = 1,600 วินาที
4,000 ข้อมูล
ตวั อย่างที่ 2.23 ข้ันตอนวิธีหนึ่งใช้เวลา 20 วินาที ในการประมวลผลข้อมูลท้ังหมด 50 ข้อมูล จงหาว่าข้ันตอนวิธีนี้
จะใช้เวลาก่ีวินาทีในการประมวลผลข้อมูลขนาด 2,000 ข้อมูล ถ้าฟังก์ชันเวลา T(n) ท่ีข้ึนอยู่กับขนาดของข้อมูล n
ของข ้ันตอนวิธีน ้ีมีอัตราการเติบโตเป็น O(n2)
วธิ ที �ำ
ถ้าฟ ังก์ชันเวลา T(n) ของขั้นต อนวิธีน ี้ มีอัตราก ารเติบโตเป็น O(n2)
แสดงว่า
ข้ันตอนวิธีนี้ ใช้เวลาในการประมวลผลข้อมูล 50 ข้อมูลท่ีแปรผันตรงกับขนาดข้อมูลในสัดส่วน 502 เป็น
20 วินาที 20002
502
ถ้าประมวลผลข้อมูล 2,000 ข้อมูลท่ีแปรผันตรงกับขนาดข้อมูลในสัดส่วน 20002 จะใช้เวลา × 20
= 32,000 วินาที
เพราะฉ ะน้ัน ขั้นตอนวิธีน้ีใช้เวลา 32,000 วินาที ในก ารป ระมวลผลข้อมูลท้ังหมด 2,000 ข้อมูล
