Data Structure & Algorithm(EP.3) — อัตราการเติบโตของฟังก์ชั่น

คำนวณหาผลรวมของตัวเลข : 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 ”

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

ตัวอย่างที่ 1

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    sum += j;
  }
}

ตัวอย่างที่ 2

for (let i = 1; i < n; i++) {
  for (let j = 3; j < n - 1; j++) {
    sum += j;
  }
}

• รูปแบบฟังก์ชั่น คือ f(n²) หรือ O(n²)
• โดยเรียกอัลกอริทึมที่มีความเร็ว O(n²) ว่า “Quadratic Time Complexity”

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

• 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)

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

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

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