Data Structure & Algorithm(EP.2) — การวัดประสิทธิภาพอัลกอริทึม
การวัดประสิทธิภาพอัลกอริทึม
เมื่อมีการพัฒนาโปรแกรมขึ้นมาจะต้องมีการวัดผลการทำงานของโปรแกรมว่าทำงานถูกต้องและได้ผลลัพธ์ตามที่ต้องการหรือไม่
เมื่อทำงานถูกต้องแล้ว มีประสิทธิภาพดีหรือไม่ ตัวอย่าง เช่น ใช้ระยะเวลาในการประมวลผลนานเท่าใด ใช้หน่วยความจำมากเกินความจำเป็นหรือไม่
การวัดประสิทธิภาพของอัลกอริทึมแบ่งออกเป็น 2 รูปแบบ
- การวิเคราะห์หน่วยความจำที่ใช้ประมวลผล (Space Complexity Analysis)
- การวิเคราะห์เวลาในการประมวลผล (Time Complexity Analysis)
การวิเคราะห์หน่วยความจำที่ใช้ประมวลผล(Space Complexity Analysis) คือ การวิเคราะห์หน่วยความจำทั้งหมดที่โปรแกรมใช้ประมวลผลอัลกอริทึม เพื่อให้ทราบถึงขนาดข้อมูลที่ต้องการป้อนหรือส่งข้อมูลเข้ามาให้อัลกอริทึมประมวลผลแล้วไม่เกิดข้อผิดพลาด การวิเคราะห์หน่วยความจำที่ใช้ประมวลผล มีองค์ประกอบอยู่ 3 ส่วน
- Instruction Space คือ ขนาดหน่วยความจำที่จำเป็นต้องใช้ ขณะคอมไพล์โปรแกรม
- Data Space คือ ขนาดหน่วยความจำที่จำเป็นต้องใช้ในการเก็บข้อมูลประเภทตัวแปรและค่าคงที่ในการประมวลผลโปรแกรม
- Environment Stack Space คือ หน่วยความจำที่ใช้สำหรับเก็บข้อมูลผลลัพธ์จากการประมวลผล
การวิเคราะห์เวลาในการประมวลผล (Time Complexity Analysis) เป็นการวิเคราะห์ขั้นตอนการประมวลผลของอัลกอริทึมในการประมาณเวลาที่ใช้ประมวลผล
หลักพิจารณาก่อนวิเคราะห์เวลาในการประมวลผล
- เมื่อประมวลผลโปรแกรมเดียวกัน คอมพิวเตอร์ที่สเปคดีกว่าจะประมวลผลได้เร็วกว่าคอมพิวเตอร์ที่สเปคต่ำหรือไม่
- เมื่อประมวลผลโปรแกรม จำนวนคำสั่งที่มีน้อยกว่าจะทำงานเร็วกว่าโปรแกรมที่มีคำสั่งมากกว่าหรือไม่
- ตัวแปรที่มีขนาดเล็กจะประมวลผลเร็วกว่าตัวแปรที่มีขนาดใหญ่หรือไม่
ประเภทของเวลาที่ใช้ประมวลผลแบ่งออกเป็น 2 ประเภท ได้แก่
- Compile Time เวลาที่ใช้ตรวจไวยากรณ์ภาษา (Syntax) ของโค้ดโปรแกรมว่าเขียนถูกต้องตามโครงสร้างภาษาที่ใช้เขียนโปรแกรมหรือไม่
- Runtime เป็นเวลาที่เครื่องคอมพิวเตอร์ใช้ประมวลผลโปรแกรม ซึ่งขึ้นอยู่กับชนิดข้อมูล จำนวนตัวแปร และจำนวนลูปที่ใช้ภายในการพัฒนาโปรแกรมที่ประมวลผล
ตัวอย่างอัลกอริทึมคำนวณหาผลรวมของตัวเลข
คำสั่งที่ 1
function summation(n){
total=0
for(i=1;i<=n;i++){
total+=i
}
return total
}คำสั่งที่ 2
function summation(n){
return n*(n+1)/2
}
อยากรู้ว่าโปรแกรมที่เขียนขึ้นมานั้นมีระยะเวลาทำงานเร็วหรือช้าจะต้องวัดประสิทธิภาพของอัลกอริทึม โดยวิเคราะห์จาก “ อัตราการเติบโตของฟังก์ชั่น ”คือ การวิเคราะห์ประสิทธิภาพของอัลกอริทึมจะดูจากอัตราการเติบโตที่เกิดขึ้นภายในฟังก์ชั่น
บทความที่เกี่ยวข้อง
- EP.1 — รู้จักกับโครงสร้างข้อมูลและอัลกอริทึม
- EP.2 — การวัดประสิทธิภาพอัลกอริทึม
- EP.3 — อัตราการเติบโตของฟังก์ชั่น
- EP.4 — การวิเคราะห์อัลกอริทึม
- EP.5 — Big-O Notation
- EP.6 — การคำนวณ Big-O
- EP.7 — ลิงค์ลิสต์ (Linked-List)
- EP.8 — สแต็ก (Stack)
- EP.9 — คิว(Queue)
- EP.10 — ทรี (Tree)
- EP.11 — Binary Search Tree (BST)
- EP.12 — กราฟ(Graphs)
