Data Structure & Algorithm(EP.4) — การวิเคราะห์อัลกอริทึม

KongRuksiam Studio

Follow

2 min readFeb 27, 2024

--

**เส้นกราฟเวลาการเติบโตตามขนาดปัญหา (n)**

การวิเคราะห์อัลกอริทึม

การวิเคราะห์อัลกอริทึมเมื่อรับขนาดปัญหาเข้ามาทำงาน (n) สิ่งที่ต้องการคือระยะเวลาในการแก้ปัญหา

ใช้เวลาน้อย -> ทำงานเร็ว
ใช้เวลามาก -> ทำงานช้า

โดยอัลกอริทึมมีขั้นตอนการทำงานได้หลายรูปแบบเพื่อใช้แก้ปัญหาแบบเดียวกัน

กรณีดีที่สุด (Best Case) คือ ใช้เวลาทำงานน้อย
กรณีแย่ที่สุด (Worst Case) คือ ใช้เวลาทำงานมาก
กรณีเฉลี่ย (Average Case) คือ ให้อัลกอริทึมทำงานหลายๆครั้ง โดยรับขนาดปัญหาที่แตกต่างกันมาหาเวลาเฉลี่ยในการทำงาน

การวัดประสิทธิภาพด้วยอัตราการเติบโตนั้นเป็นการวิเคราะห์อัลกอริทึมโดยใช้เครื่องหมายมาเป็นเครื่องมือในการวัดประสิทธิภาพอัลกอริทึม เช่น Big-O , Big-Omega , Big-Teta เป็นต้น

กรณีที่แย่ที่สุด จะใช้เครื่องหมาย Big-O
กรณีที่ดีที่สุด จะใช้เครื่องหมาย Big-Ω (Omega)
กรณีเฉลี่ย จะใช้เครื่องหมาย Big-Θ (Teta)

รู้จักกับ Big-O

วิธีที่เป็นมาตรฐานในการวิเคราะห์อัลกอริธึมในการระบุถึงเวลาที่อัลกอริธึมใช้เมื่อเทียบกับขนาดข้อมูลรับเข้า (Time Complexity)
ระยะเวลาที่แย่ที่สุดที่คอมพิวเตอร์ต้องทำงานกับความซับซ้อนในการใช้งานอัลกอริทึม
เป็นการวัดประสิทธิภาพเชิงเวลาในการวิเคราะห์การประมวลผลอัลกอริทึมในกรณีที่ใช้เวลานานที่สุด

การนับตัวดำเนินการ (Operation Counts)

คือ การนับจำนวนครั้งการทำงานของตัวดำเนินการในอัลกอริทึม ซึ่งมี 4 รูปแบบ คือ

แบบค่าคงที่ (Constant) พิจารณาขั้นตอนการดำเนินการของอัลกอริทึม ซึ่งแต่ละขั้นตอนจะนับการทำงานเป็น 1 ครั้ง

let count = 0 
let total = (1+n) * (n/2)

//ผลรวมของฟังก์ชั่น f(n) = 1+1 = 2  หรือ O(f(n)) = O(2)

แบบลูปลำดับ (Linear Loop) พิจารณาจากจำนวนการทำงานของตัวดำเนินการภายในลูปของอัลกอริทึม

function sum(n=3) {
  let total = 0; //1
  for (let i = 1; i < n; i++) { //n
    total = total + 1; //n-1
  }
}

//ผลรวมของฟังก์ชั่น f(n) = 1+n+n-1 = 2n  หรือ O(f(n)) = O(2n)

แบบลูปลอการิทึม (Logarithmic Loop) ทำงานคล้ายกับลูปแบบลำดับ แต่จะใช้ค่าตัวแปรทำหน้าที่ในการเพิ่มหรือลดด้วยการคูณหรือหารเป็นอัตราเท่าตัว

function calculate() {
  let total = 0; //1
  for (let i = 1; i < 10; i=i*2) { //log2n+1
    // log2n
    // log2n
  }
}

/*
ผลรวมของฟังก์ชั่น 
f(n) = 1+log2n+1 + log2n + log2n 
     = 3 log2n+2  หรือ O(f(n)) = O(3 log2n+2)
*/

แบบลูปซ้อน (Nested Loop) มีลักษณะเป็นลูปซ้อนลูป พิจารณาการทำงานจากจำนวนลูปนอกและลูปใน

let total = 0; //1
for (let i = 0; i < n; i++) { //n+1
  for (let j = 0; j < n; j++) { //n(n+1) = n^2 + n
      //n^2
      //n^2
  }
}
/*
ผลรวมของฟังก์ชั่น  f(n) = 1 + n+1 + n(n+1) + n^2+ n^2
               f(n) = 3n^2+2n+2
*/

การเขียนลดรูปฟังก์ชั่น O(f(n))

O(500) → O(1)
O(2n) → O(n)
O(n+10) → O(n)
O(1000n+50) → O(n)
O(n²+5n+8) → O(n²)
O(13n²) → O(n²)
O (n²+n³) → O(n³)
O (n+n+n+n) → O(n)
O (n+10) → O(n)
O (100xn) → O(n)

บทความที่เกี่ยวข้อง

เนื้อหาที่เกี่ยวข้อง

ช่องทางการสนับสนุน
🎓 คอร์สพัฒนาเว็บด้วย JavaScript 40 Workshop

🌎 ติดตามข่าวสารเพิ่มเติมได้ที่
Facebook | YouTube | TikTok