Data Structure & Algorithm(EP.5) — 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)

ตัวอย่างอัลกอริทึม

function firstElement(array){
    return array[0]// O(1)
}
let score = [70, 30, 15, 90, 50];
console.log(firstElement(score)); // 70

Logarithm Time : O(log n) เป็น Big-O ที่นำไปใช้ในการวนลูปและตัดจำนวนข้อมูลที่ไม่มีโอกาสเกิดขึ้นออกไปทีละครึ่งโดยแบ่งครึ่งข้อมูลไปเรื่อย ๆ ซึ่งสามารถพบการใช้งาน O(log n) ในการค้นหาข้อมูลที่เรียกว่า Binary Search ซึ่งเป็นการค้นหาแบบค่อย ๆ แบ่งครึ่งไปเรื่อย ๆ

Logarithm Time : O(log n)

function binarySearch(array, value) {
  let firstIndex = 0;
  let lastIndex = array.length - 1;
  while (firstIndex <= lastIndex) {
    let middleIndex = Math.floor((firstIndex + lastIndex) / 2);
    if (array[middleIndex] === value) {
      return middleIndex;
    }
    if (array[middleIndex] > value) {
      lastIndex = middleIndex - 1;
    } else {
      firstIndex = middleIndex + 1;
    }
  }
  return -1;
}

let score = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59];
console.log(binarySearch(score, 37));

Linear Time: O(n) เป็น Big-O ที่ใช้ระยะเวลาทำงานอ้างอิงตามปริมาณข้อมูลที่มี ถ้ามีข้อมูลมากยิ่งใช้เวลามาก โดย Worst Case จะไม่เกินปริมาณข้อมูลที่ส่งมา

Linear Time: O(n)

function search(array, value) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === value) {
      return i;
    }
  }
  return -1;
}
let score = [12, 22, 45, 67, 96];
console.log(search(score, 100));

Quadratic Time : O(n2) เป็น Big-O ที่อ้างอิงการทำงานตามการเพิ่มขนาดของ input (n) ที่ส่งเข้ามา 2 เท่า ส่งผลให้ระยะเวลาทำงานเพิ่มขึ้น 4 เท่า เช่น การใช้งานลูปซ้ำกัน 2 ชั้น เป็นต้น

Quadratic Time : O(n2)

function matchElement(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      if (i !== j && array[i] === array[j]) {
        return `ตำแหน่งซ้ำกัน คือ ${i} และ ${j}`;
      }
    }
  }
  return "ไม่มีค่าซ้ำกันเลย";
}

const fruit = ["ส้ม", "มะละกอ", "มังคุด", "ทุเรียน", "ส้ม", "แตงกวา"];
console.log(matchElement(fruit)); // ตำแหน่งซ้ำกัน คือ 0 และ 4

Exponential Time : O(2^n) เป็น Big-O ที่ใช้จำนวนข้อมูลแค่นิดเดียว แต่ใช้เวลาประมวลผลนานและเพิ่มอัตราการเติบโตเป็นเท่าตัว ยกตัวอย่างถ้า n = 4 ก็ทำงาน 16 รอบ ถ้า n = 8 ใช้ไป 256 รอบ เช่น ฟังก์ชั่นฟีโบนัชชี เป็นต้น

Exponential Time : O(2^n)

function fibonacci(n) {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 2) + fibonacci(n - 1);
  }
}
console.log(fibonacci(6)); // 8

Factorial Time : O(n!) เป็น Big-O เคสที่แย่ที่สุดใช้เวลาประมวลผลนานและเพิ่มอัตราการเติบโตเป็นเท่าตัว เช่น ถ้า n = 5 ก็มีค่าเท่ากับ 5! หรือ 5x4x3x2x1 ทำงาน 120 รอบ

Factorial Time : O(n!)

function factorial(n) {
  if (n == 1) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}
console.log(factorial(5)); // 120

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

• 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