Data Structure & Algorithm(ตอนที่ 2) — การวัดประสิทธิภาพอัลกอริทึม & Big O
การวัดประสิทธิภาพอัลกอริทึม
เมื่อมีการพัฒนาโปรแกรมขึ้นมาจะต้องมีการวัดผลการทำงานของโปรแกรมว่าทำงานถูกต้องและได้ผลลัพธ์ตามที่ต้องการหรือไม่
เมื่อทำงานถูกต้องแล้ว มีประสิทธิภาพดีหรือไม่ ตัวอย่าง เช่น ใช้ระยะเวลาในการประมวลผลนานเท่าใด ใช้หน่วยความจำมากเกินความจำเป็นหรือไม่
การวัดประสิทธิภาพของอัลกอริทึมแบ่งออกเป็น 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+2+3+4+5+…..n = ?
ขั้นตอนการวิเคราะห์อัตราการเติบโต
- ■เขียนอัลกอริทึม
- ■เลือกคำสั่งตัวแทนที่ใช้ (คำสั่งที่ถูกทำงานและแปรผันตามเวลาทำงาน)
- ■วิเคราะห์จำนวนครั้งที่คำสั่งทำงาน
- ■หาฟังก์ชั่นของจำนวนครั้งที่คำสั่งทำงานกับปริมาณข้อมูล
1+2+3+4+5+…..n = ?
หาผลรวมของ 1+2+3 ต้องบวกทั้งหมด 2 ครั้ง
หาผลรวมของ 1+2+3+4 ต้องบวกทั้งหมด 3 ครั้ง
หาผลรวมของ 1+2+3+4+5 ต้องบวกทั้งหมด 4 ครั้ง
หาผลรวมของ 1+2+3+….n ต้องบวกทั้งหมด n-1 ครั้ง
จำนวนครั้งที่ทำงาน คือ n-1
- ■รูปแบบฟังก์ชั่น คือ f(n-1) หรือ O(n-1)
- ■เขียนแบบลดรูป คือ O(n)
- ■โดยเรียกอัลกอริทึมที่มีความเร็ว O(n) ว่า “ Linear Time Complexity ”
การวิเคราะห์อัลกอริทึม
เส้นกราฟเวลาการเติบโตตามขนาดปัญหา (n)
การวิเคราะห์อัลกอริทึม
การวิเคราะห์อัลกอริทึมเมื่อรับขนาดปัญหาเข้ามาทำงาน (n) สิ่งที่ต้องการคือระยะเวลาในการแก้ปัญหา
- ■ใช้เวลาน้อย -> ทำงานเร็ว
- ■ใช้เวลามาก -> ทำงานช้า
โดยอัลกอริทึมมีขั้นตอนการทำงานได้หลายรูปแบบเพื่อใช้แก้ปัญหาแบบเดียวกัน
- ■กรณีดีที่สุด (Best Case) คือ ใช้เวลาทำงานน้อย
- ■กรณีแย่ที่สุด (Worst Case) คือ ใช้เวลาทำงานมาก
- ■กรณีเฉลี่ย (Average Case) คือ ให้อัลกอริทึมทำงานหลายๆครั้ง โดยรับขนาดปัญหาที่แตกต่างกันมาหาเวลาเฉลี่ยในการทำงาน
การวัดประสิทธิภาพด้วยอัตราการเติบโตนั้นเป็นการวิเคราะห์อัลกอริทึมโดยใช้เครื่องหมายมาเป็นเครื่องมือในการวัดประสิทธิภาพอัลกอริทึม เช่น Big-O , Big-Omega , Big-Teta เป็นต้น
- ■กรณีที่แย่ที่สุด จะใช้เครื่องหมาย Big-O
- ■กรณีที่ดีที่สุด จะใช้เครื่องหมาย Big-Ω (Omega)
- ■กรณีเฉลี่ย จะใช้เครื่องหมาย Big-Θ (Teta)
รู้จักกับ Big-O
- ■วิธีที่เป็นมาตรฐานในการวิเคราะห์อัลกอริธึมในการระบุถึงเวลาที่อัลกอริธึมใช้เมื่อเทียบกับขนาดข้อมูลรับเข้า (Time Complexity)
- ■ระยะเวลาที่แย่ที่สุดที่คอมพิวเตอร์ต้องทำงานกับความซับซ้อนในการใช้งานอัลกอริทึม
- ■เป็นการวัดประสิทธิภาพเชิงเวลาในการวิเคราะห์การประมวลผลอัลกอริทึมในกรณีที่ใช้เวลานานที่สุด
Big-O Notation
รู้จักกับ Big-O
- ■วิธีที่เป็นมาตรฐานในการวิเคราะห์อัลกอริธึมในการระบุถึงเวลาที่อัลกอริธึมใช้เมื่อเทียบกับขนาดข้อมูลรับเข้า (Time Complexity)
- ■ระยะเวลาที่แย่ที่สุดที่คอมพิวเตอร์ต้องทำงานกับความซับซ้อนในการใช้อัลกอริทึม
- ■เป็นการวัดประสิทธิภาพเชิงเวลาในการวิเคราะห์การประมวลผลอัลกอริทึมในกรณีที่ใช้เวลานานที่สุด
Big-O Notation
ตัวอย่างฟังก์ชั่น O(n²) = Quadratic
- ●n²+n
- ●4n²+3n+12
- ●2n²+7
ตัวอย่างฟังก์ชั่น O(n³) = Cubic
- ●n³+n²+n
- ●4n³+3n+12
- ●2n³+7
ตารางเปรียบเทียบประสิทธิภาพ
n = จำนวนข้อมูล
ตารางเปรียบเทียบประสิทธิภาพ
Constant: O(1) เป็น Big-O ที่ดีที่สุด ไม่ว่าปริมาณของข้อมูลจะมากเท่าใด ระยะเวลาในการประมวลผลจะไม่เปลี่ยนแปลง เช่น 1 จำนวน หรือ 1 ล้านจำนวน จะมีค่าเท่ากับ 1 เสมอ Constant Time เวลาคงที่ไม่ขึ้นกับ input size (n)
Constant : O(1)
Logarithm Time : O(log n) เป็น Big-O ที่นำไปใช้ในการวนลูปและตัดจำนวนข้อมูลที่ไม่มีโอกาสเกิดขึ้นออกไปทีละครึ่งโดยแบ่งครึ่งข้อมูลไปเรื่อย ๆ ซึ่งสามารถพบการใช้งาน O(log n) ในการค้นหาข้อมูลที่เรียกว่า Binary Search ซึ่งเป็นการค้นหาแบบค่อย ๆ แบ่งครึ่งไปเรื่อย ๆ
Logarithm Time : O(log n)
Linear Time: O(n) เป็น Big-O ที่ใช้ระยะเวลาทำงานอ้างอิงตามปริมาณข้อมูลที่มี ถ้ามีข้อมูลมากยิ่งใช้เวลามาก โดย Worst Case จะไม่เกินปริมาณข้อมูลที่ส่งมา
Linear Time: O(n)
Quadratic Time : O(n2) เป็น Big-O ที่อ้างอิงการทำงานตามการเพิ่มขนาดของ input (n) ที่ส่งเข้ามา 2 เท่า ส่งผลให้ระยะเวลาทำงานเพิ่มขึ้น 4 เท่า เช่น การใช้งานลูปซ้ำกัน 2 ชั้น เป็นต้น
Quadratic Time : O(n2)
Exponential Time : O(2^n) เป็น Big-O ที่ใช้จำนวนข้อมูลแค่นิดเดียว แต่ใช้เวลาประมวลผลนานและเพิ่มอัตราการเติบโตเป็นเท่าตัว ยกตัวอย่างถ้า n = 4 ก็ทำงาน 16 รอบ ถ้า n = 8 ใช้ไป 256 รอบ เช่น ฟังก์ชั่นฟีโบนัชชี เป็นต้น
Exponential Time : O(2^n)
Factorial Time : O(n!) เป็น Big-O เคสที่แย่ที่สุดใช้เวลาประมวลผลนานและเพิ่มอัตราการเติบโตเป็นเท่าตัว เช่น ถ้า n = 5 ก็มีค่าเท่ากับ 5! หรือ 5x4x3x2x1 ทำงาน 120 รอบ
Factorial Time : O(n!)
เนื้อหาที่เกี่ยวข้อง
➤ ติดตามข่าวสารเพิ่มเติมได้ที่ :
- ■
- ■
- ■
- ■คอร์สเรียน : https://www.udemy.com/user/kong-ruksiam/
- ■ซื้อของผ่าน Shopee : https://shope.ee/3plB9kVnPd
โฆษณา
- ดาวน์โหลดแอปพลิเคชัน
- © 2024 Blockdit
