Fundamentalsบทที่ 1Big-O Notation

บิ๊กโอ (Big-O notation): คู่มือฉบับเริ่มต้นแบบละเอียด

บทเรียนนี้สอนตั้งแต่ภาพรวมไปถึงการวิเคราะห์โค้ดทีละขั้น โดยเน้นให้เข้าใจว่า บิ๊กโอ (Big-O notation) สนใจแนวโน้มการเติบโตของเวลาและทรัพยากรเมื่ออินพุต (Input) โตขึ้น ไม่ใช่เวลาจริงเป็นวินาทีบนเครื่องใดเครื่องหนึ่ง

1. Big-O notation คืออะไร

บิ๊กโอ (Big-O notation) คือวิธีอธิบายว่าอัลกอริทึม (Algorithm) จะใช้เวลาทำงานหรือทรัพยากรเพิ่มขึ้นอย่างไร เมื่อขนาดอินพุต (Input Size: n) เพิ่มขึ้นเรื่อย ๆ

เราไม่ได้ถามว่าโค้ดนี้ใช้เวลา 0.01 วินาทีหรือ 0.02 วินาที แต่ถามว่าเมื่อข้อมูลโตจากหลักสิบเป็นหลักล้าน โค้ดจะโตแบบค่อย ๆ หรือพุ่งแรงแค่ไหน

2. ทำไมเราต้องวิเคราะห์ประสิทธิภาพของอัลกอริทึม

เพื่อเลือกวิธีที่โตช้ากว่า

ตอนข้อมูลเล็ก วิธีต่างกันอาจดูไม่ชัด แต่เมื่อข้อมูลโต วิธีที่อัตราการเติบโต (Growth Rate) ดีกว่าจะช่วยประหยัดเวลามหาศาล

เพื่อป้องกันปัญหาในระบบจริง

ระบบที่รับผู้ใช้จำนวนมาก ถ้าใช้อัลกอริทึมไม่เหมาะ อาจช้า ค้าง หรือกินทรัพยากรจนระบบล่มได้

3. Big-O บอกอะไร และไม่ได้บอกอะไร

บอกอะไร

บอกแนวโน้มการเติบโตของจำนวนงาน เช่น O(1), O(log n), O(n), O(n^2) เมื่อ n ใหญ่ขึ้น

ไม่ได้บอกอะไร

ไม่ได้บอกเวลาจริงแบบเป๊ะเป็นวินาที และไม่ได้สะท้อนความเร็วเครื่อง, ภาษาโปรแกรม หรือสภาพแวดล้อมรันไทม์ (Runtime)

4. ตัวอย่างจากชีวิตจริง

หาเบอร์โทรในสมุดรายชื่อ

ถ้าไม่มีการเรียงชื่อ เราอาจต้องไล่ทีละชื่อ (เส้นตรง). ถ้าเรียงชื่อแล้วและเปิดกลางเล่มก่อน จะตัดครึ่งการค้นหาได้เรื่อย ๆ

เช็กชื่อนักเรียนหน้าห้อง

ถ้าต้องเช็กทุกคน 1 รอบ งานจะโตตามจำนวนนักเรียนโดยตรง

จับคู่เพื่อนทุกคนให้ทักกัน

ถ้ามี n คน และให้ทุกคนทักทุกคน จำนวนคู่จะโตเร็วมากแบบกำลังสอง

5. แนวคิดเรื่อง input size

อินพุตไซซ์ (Input Size: n) คือปริมาณข้อมูลที่เข้าอัลกอริทึม เช่น จำนวนสมาชิกในอาเรย์ ความยาวสตริง หรือจำนวนโหนดในกราฟ

เวลาเราบอกว่าอัลกอริทึมเป็น O(n) หมายถึง "ถ้า n โต งานก็โตตาม n" ไม่ได้ระบุค่าคงที่ตายตัวในแต่ละเครื่อง

6. แนวคิดเรื่องอัตราการเติบโต (growth rate)

อัตราการเติบโต (Growth Rate) คือภาพว่าเมื่อข้อมูลเพิ่ม งานเพิ่มเร็วแค่ไหน นี่คือหัวใจของบิ๊กโอ (Big-O notation)

ตัวอย่างเช่น O(log n) โตช้ากว่า O(n) และ O(n) โตช้ากว่า O(n^2) มากเมื่อ n มีขนาดใหญ่

7. ทำไมละค่าคงที่ได้

เพราะบิ๊กโอ (Big-O notation) สนใจแนวโน้มเมื่อ n ใหญ่มาก ไม่ได้สนใจจูนระดับ micro-optimization ตัวอย่างเช่น 3n กับ n เมื่อ n ใหญ่มาก ทั้งคู่ยังโตแบบเส้นตรง จึงจัดอยู่ในกลุ่ม O(n)

ตัวอย่างการตัดค่าคงที่bash

มองกลุ่มการเติบโต ไม่มองตัวเลขคงที่เล็ก ๆ

T(n) = 3n + 10
ตัดค่าคงที่และค่าสัมประสิทธิ์ -> O(n)

8. ทำไมสนใจพจน์ที่โตเร็วที่สุด

เมื่อ n ใหญ่มาก พจน์ที่โตเร็วสุดจะครองผลรวม ตัวอย่าง n^2 + n + 5 เมื่อ n โตมาก พจน์ n^2 มีผลหลักที่สุด จึงสรุปเป็น O(n^2)

ตัวอย่างเลือกพจน์หลักbash

หลักคิดนี้ใช้แทบทุกครั้งในการวิเคราะห์ Big-O

T(n) = n^2 + n + 5
เมื่อ n ใหญ่ -> n^2 เด่นที่สุด
ดังนั้น -> O(n^2)

9. ตัวอย่าง Big-O พื้นฐาน

O(1)

งานคงที่ เช่น เข้าถึงข้อมูลตำแหน่งเฉพาะ

O(log n)

งานโตช้า เพราะลดปัญหาครึ่งหนึ่งทุกรอบ

O(n)

งานโตตามจำนวนข้อมูลโดยตรง

O(n log n)

มักเจอในอัลกอริทึมแบ่งแล้วรวม เช่น เมิร์จซอร์ต (Merge Sort)

O(n^2)

โตเร็ว มักเกิดจากลูปซ้อนเทียบข้อมูลหลายคู่

O(2^n)

โตแบบเอ็กซ์โปเนนเชียล เร็วจนใช้งานยากเมื่อ n ใหญ่

10. ตัวอย่างโค้ด JavaScript ของแต่ละแบบ พร้อมวิเคราะห์ทีละขั้น

O(1)

O(1) - อ่านสมาชิกตำแหน่งที่กำหนด

เป้าหมาย: เข้าถึงข้อมูลแบบตรงจุด

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function getLast(items) {
  return items[items.length - 1];
}

ไม่ว่ามีข้อมูล 10 หรือ 1,000,000 ตัว โค้ดหลักยังทำงานใกล้เคียงเดิม
อ่านตำแหน่งเดียว แล้วคืนค่า
ดังนั้นเวลาเป็นค่าคงที่ -> O(1)

O(log n)

O(log n) - ค้นหาแบบหารครึ่ง

เป้าหมาย: ลดขนาดปัญหาเป็นครึ่งหนึ่งทุกครั้ง

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

แต่ละรอบของลูป ตัดข้อมูลทิ้งครึ่งหนึ่ง
จำนวนรอบจะเพิ่มช้ามากเมื่อข้อมูลโต
รูปแบบนี้เป็นลายเซ็นของ O(log n)

O(n)

O(n) - เดินผ่านข้อมูลหนึ่งรอบ

เป้าหมาย: อ่านทุกสมาชิกเพื่อหาผลรวม

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function sumAll(items) {
  let total = 0;

  for (const item of items) {
    total += item;
  }

  return total;
}

ลูปทำงานตามจำนวนสมาชิกทั้งหมด
n โต 2 เท่า จำนวนงานโตใกล้เคียง 2 เท่า
จึงเป็น O(n)

O(n log n)

O(n log n) - ผสมการแบ่งครึ่ง + รวมผล

เป้าหมาย: ตัวอย่างแนวคิดของเมิร์จซอร์ต

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function mergeSort(items) {
  if (items.length <= 1) return items;

  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid));
  const right = mergeSort(items.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return result.concat(left.slice(i), right.slice(j));
}

แบ่งข้อมูลครึ่งต่อครึ่ง -> ส่วน log n
แต่ละชั้นของการแบ่งต้องรวมข้อมูลรวมกันประมาณ n งาน
จึงได้ n คูณ log n -> O(n log n)

O(n^2)

O(n^2) - ลูปซ้อนสองชั้น

เป้าหมาย: เทียบค่าทุกคู่เพื่อหาเลขซ้ำ

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function hasDuplicate(items) {
  for (let i = 0; i < items.length; i += 1) {
    for (let j = i + 1; j < items.length; j += 1) {
      if (items[i] === items[j]) {
        return true;
      }
    }
  }

  return false;
}

ลูปนอกวิ่งใกล้เคียง n รอบ
ลูปในวิ่งตามลูปนอกหลายรอบ รวมแล้วใกล้เคียง n คูณ n
จึงเป็น O(n^2)

O(2^n)

O(2^n) - เรียกซ้ำแตกกิ่ง

เป้าหมาย: ตัวอย่างฟีโบนัชชีแบบไม่เก็บผลลัพธ์

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

ทุกครั้งที่เรียก fib(n) จะแตกเป็นสองกิ่งหลัก
จำนวนการเรียกซ้ำพุ่งเร็วมากเมื่อ n เพิ่ม
โดยประมาณเป็นการเติบโตแบบเอ็กซ์โปเนนเชียล -> O(2^n)

11. วิธีดู Big-O จาก loop เดี่ยว

ตัวอย่าง loop เดี่ยวJS

ลูปวิ่งครบข้อมูลหนึ่งรอบ

function printItems(items) {
  for (let i = 0; i < items.length; i += 1) {
    console.log(items[i]);
  }
}

ลูปวิ่งตามจำนวนสมาชิกทั้งหมด ถ้า n เพิ่มขึ้น จำนวนรอบเพิ่มตามนั้นตรง ๆ จึงเป็น O(n)

12. วิธีดู Big-O จาก nested loop

ตัวอย่าง nested loopJS

ลูปนอกและลูปในคูณกัน

function printPairs(items) {
  for (let i = 0; i < items.length; i += 1) {
    for (let j = 0; j < items.length; j += 1) {
      console.log(items[i], items[j]);
    }
  }
}

ลูปนอกประมาณ n รอบ และทุกรอบของลูปนอกมีลูปในประมาณ n รอบ งานรวมจึงเป็น n คูณ n = O(n^2)

13. วิธีดู Big-O จากการหารครึ่งข้อมูล

ตัวอย่างลดข้อมูลครึ่งหนึ่งทุกรอบJS

รูปแบบนี้มักจบที่ O(log n)

function reduceByHalf(n) {
  let size = n;

  while (size > 1) {
    size = Math.floor(size / 2);
  }
}

ทุกครั้งที่วนลูป ขนาดปัญหาลดเหลือครึ่งหนึ่ง จึงใช้จำนวนรอบประมาณ log n และสรุปเป็น O(log n)

14. ข้อผิดพลาดที่พบบ่อย

คิดว่าบิ๊กโอ (Big-O notation) คือเวลาจริงเป็นวินาทีบนเครื่องของเรา

คิดว่า O(1) แปลว่าเร็วเสมอทุกกรณี ทั้งที่ค่าคงที่จริงอาจสูง

เห็นลูปสองชั้นแล้วสรุป O(n^2) ทันที ทั้งที่บางครั้งลูปในไม่ครบ n ทุกครั้ง

ลืมแยกว่าเรากำลังวิเคราะห์เวลา (Time Complexity) หรือหน่วยความจำ (Space Complexity)

สับสนระหว่างกรณีดีที่สุด (Best Case) กับกรณีแย่ที่สุด (Worst Case)

15. สรุปเปรียบเทียบ Big-O แต่ละแบบ

รูปแบบ	ลักษณะการโต	ตัวอย่างงาน
O(1)	คงที่	อ่านค่าตำแหน่งที่รู้ index
O(log n)	โตช้า	ค้นหาแบบหารครึ่ง
O(n)	โตตามข้อมูล	เดินครบหนึ่งรอบ
O(n log n)	กลาง ๆ สำหรับงานเรียงที่ดี	เมิร์จซอร์ต
O(n^2)	โตเร็ว	ลูปซ้อนสองชั้น
O(2^n)	พุ่งแรงมาก	แตกกิ่ง recursion แบบไม่เก็บผล

16. สรุปท้ายบทแบบจำง่าย

บิ๊กโอ (Big-O notation) คือเครื่องมือเปรียบเทียบแนวโน้มการเติบโตของงาน เมื่ออินพุตใหญ่ขึ้น โดยไม่ยึดติดเวลาจริงบนเครื่องใดเครื่องหนึ่ง

หลักจำสั้น ๆ คือ ตัดค่าคงที่ เลือกพจน์ที่โตเร็วสุด และให้ความสำคัญกับ อัตราการเติบโต (Growth Rate) มากกว่าตัวเลขเล็ก ๆ ระยะสั้น

ถ้าต้องตัดสินใจระหว่างหลายวิธี ให้ถามเสมอว่าเมื่อข้อมูลโต 100 เท่า วิธีไหนยังรับไหวกว่า

17. แบบฝึกหัด 4 ข้อ พร้อมแนวเฉลย

ภาพประกอบการเติบโต

ภาพที่ 1: กราฟเปรียบเทียบการเติบโตของ O(1), O(log n), O(n), และ O(n^2) เมื่อขนาดอินพุตเพิ่มขึ้น จะเห็นว่า O(n^2) พุ่งขึ้นเร็วมากที่สุด

ภาพที่ 2: เมื่ออินพุตโตจาก 10 เป็น 1000 งานของ O(log n) เพิ่มน้อยมาก แต่ O(n^2) โตแบบกระโดด นี่คือเหตุผลที่บิ๊กโอ (Big-O notation) สำคัญกับงานข้อมูลขนาดใหญ่

Fundamentalsบทที่ 1Big-O Notation

บิ๊กโอ (Big-O notation): คู่มือฉบับเริ่มต้นแบบละเอียด

1. Big-O notation คืออะไร

2. ทำไมเราต้องวิเคราะห์ประสิทธิภาพของอัลกอริทึม

เพื่อเลือกวิธีที่โตช้ากว่า

เพื่อป้องกันปัญหาในระบบจริง

3. Big-O บอกอะไร และไม่ได้บอกอะไร

บอกอะไร

บอกแนวโน้มการเติบโตของจำนวนงาน เช่น O(1), O(log n), O(n), O(n^2) เมื่อ n ใหญ่ขึ้น

ไม่ได้บอกอะไร

4. ตัวอย่างจากชีวิตจริง

หาเบอร์โทรในสมุดรายชื่อ

เช็กชื่อนักเรียนหน้าห้อง

ถ้าต้องเช็กทุกคน 1 รอบ งานจะโตตามจำนวนนักเรียนโดยตรง

จับคู่เพื่อนทุกคนให้ทักกัน

ถ้ามี n คน และให้ทุกคนทักทุกคน จำนวนคู่จะโตเร็วมากแบบกำลังสอง

5. แนวคิดเรื่อง input size

6. แนวคิดเรื่องอัตราการเติบโต (growth rate)

ตัวอย่างเช่น O(log n) โตช้ากว่า O(n) และ O(n) โตช้ากว่า O(n^2) มากเมื่อ n มีขนาดใหญ่

7. ทำไมละค่าคงที่ได้

ตัวอย่างการตัดค่าคงที่bash

มองกลุ่มการเติบโต ไม่มองตัวเลขคงที่เล็ก ๆ

T(n) = 3n + 10
ตัดค่าคงที่และค่าสัมประสิทธิ์ -> O(n)

8. ทำไมสนใจพจน์ที่โตเร็วที่สุด

ตัวอย่างเลือกพจน์หลักbash

หลักคิดนี้ใช้แทบทุกครั้งในการวิเคราะห์ Big-O

T(n) = n^2 + n + 5
เมื่อ n ใหญ่ -> n^2 เด่นที่สุด
ดังนั้น -> O(n^2)

9. ตัวอย่าง Big-O พื้นฐาน

O(1)

งานคงที่ เช่น เข้าถึงข้อมูลตำแหน่งเฉพาะ

O(log n)

งานโตช้า เพราะลดปัญหาครึ่งหนึ่งทุกรอบ

O(n)

งานโตตามจำนวนข้อมูลโดยตรง

O(n log n)

มักเจอในอัลกอริทึมแบ่งแล้วรวม เช่น เมิร์จซอร์ต (Merge Sort)

O(n^2)

โตเร็ว มักเกิดจากลูปซ้อนเทียบข้อมูลหลายคู่

O(2^n)

โตแบบเอ็กซ์โปเนนเชียล เร็วจนใช้งานยากเมื่อ n ใหญ่

10. ตัวอย่างโค้ด JavaScript ของแต่ละแบบ พร้อมวิเคราะห์ทีละขั้น

O(1)

O(1) - อ่านสมาชิกตำแหน่งที่กำหนด

เป้าหมาย: เข้าถึงข้อมูลแบบตรงจุด

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function getLast(items) {
  return items[items.length - 1];
}

ไม่ว่ามีข้อมูล 10 หรือ 1,000,000 ตัว โค้ดหลักยังทำงานใกล้เคียงเดิม
อ่านตำแหน่งเดียว แล้วคืนค่า
ดังนั้นเวลาเป็นค่าคงที่ -> O(1)

O(log n)

O(log n) - ค้นหาแบบหารครึ่ง

เป้าหมาย: ลดขนาดปัญหาเป็นครึ่งหนึ่งทุกครั้ง

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function binarySearch(sorted, target) {
  let left = 0;
  let right = sorted.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

แต่ละรอบของลูป ตัดข้อมูลทิ้งครึ่งหนึ่ง
จำนวนรอบจะเพิ่มช้ามากเมื่อข้อมูลโต
รูปแบบนี้เป็นลายเซ็นของ O(log n)

O(n)

O(n) - เดินผ่านข้อมูลหนึ่งรอบ

เป้าหมาย: อ่านทุกสมาชิกเพื่อหาผลรวม

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function sumAll(items) {
  let total = 0;

  for (const item of items) {
    total += item;
  }

  return total;
}

ลูปทำงานตามจำนวนสมาชิกทั้งหมด
n โต 2 เท่า จำนวนงานโตใกล้เคียง 2 เท่า
จึงเป็น O(n)

O(n log n)

O(n log n) - ผสมการแบ่งครึ่ง + รวมผล

เป้าหมาย: ตัวอย่างแนวคิดของเมิร์จซอร์ต

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function mergeSort(items) {
  if (items.length <= 1) return items;

  const mid = Math.floor(items.length / 2);
  const left = mergeSort(items.slice(0, mid));
  const right = mergeSort(items.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }

  return result.concat(left.slice(i), right.slice(j));
}

แบ่งข้อมูลครึ่งต่อครึ่ง -> ส่วน log n
แต่ละชั้นของการแบ่งต้องรวมข้อมูลรวมกันประมาณ n งาน
จึงได้ n คูณ log n -> O(n log n)

O(n^2)

O(n^2) - ลูปซ้อนสองชั้น

เป้าหมาย: เทียบค่าทุกคู่เพื่อหาเลขซ้ำ

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function hasDuplicate(items) {
  for (let i = 0; i < items.length; i += 1) {
    for (let j = i + 1; j < items.length; j += 1) {
      if (items[i] === items[j]) {
        return true;
      }
    }
  }

  return false;
}

ลูปนอกวิ่งใกล้เคียง n รอบ
ลูปในวิ่งตามลูปนอกหลายรอบ รวมแล้วใกล้เคียง n คูณ n
จึงเป็น O(n^2)

O(2^n)

O(2^n) - เรียกซ้ำแตกกิ่ง

เป้าหมาย: ตัวอย่างฟีโบนัชชีแบบไม่เก็บผลลัพธ์

CodeJS

อ่านโค้ดก่อน แล้วไล่วิเคราะห์ตามขั้นตอน

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

ทุกครั้งที่เรียก fib(n) จะแตกเป็นสองกิ่งหลัก
จำนวนการเรียกซ้ำพุ่งเร็วมากเมื่อ n เพิ่ม
โดยประมาณเป็นการเติบโตแบบเอ็กซ์โปเนนเชียล -> O(2^n)

11. วิธีดู Big-O จาก loop เดี่ยว

ตัวอย่าง loop เดี่ยวJS

ลูปวิ่งครบข้อมูลหนึ่งรอบ

function printItems(items) {
  for (let i = 0; i < items.length; i += 1) {
    console.log(items[i]);
  }
}

12. วิธีดู Big-O จาก nested loop

ตัวอย่าง nested loopJS

ลูปนอกและลูปในคูณกัน

function printPairs(items) {
  for (let i = 0; i < items.length; i += 1) {
    for (let j = 0; j < items.length; j += 1) {
      console.log(items[i], items[j]);
    }
  }
}

13. วิธีดู Big-O จากการหารครึ่งข้อมูล

ตัวอย่างลดข้อมูลครึ่งหนึ่งทุกรอบJS

รูปแบบนี้มักจบที่ O(log n)

function reduceByHalf(n) {
  let size = n;

  while (size > 1) {
    size = Math.floor(size / 2);
  }
}

14. ข้อผิดพลาดที่พบบ่อย

คิดว่าบิ๊กโอ (Big-O notation) คือเวลาจริงเป็นวินาทีบนเครื่องของเรา

คิดว่า O(1) แปลว่าเร็วเสมอทุกกรณี ทั้งที่ค่าคงที่จริงอาจสูง

เห็นลูปสองชั้นแล้วสรุป O(n^2) ทันที ทั้งที่บางครั้งลูปในไม่ครบ n ทุกครั้ง

ลืมแยกว่าเรากำลังวิเคราะห์เวลา (Time Complexity) หรือหน่วยความจำ (Space Complexity)

สับสนระหว่างกรณีดีที่สุด (Best Case) กับกรณีแย่ที่สุด (Worst Case)

15. สรุปเปรียบเทียบ Big-O แต่ละแบบ

รูปแบบ	ลักษณะการโต	ตัวอย่างงาน
O(1)	คงที่	อ่านค่าตำแหน่งที่รู้ index
O(log n)	โตช้า	ค้นหาแบบหารครึ่ง
O(n)	โตตามข้อมูล	เดินครบหนึ่งรอบ
O(n log n)	กลาง ๆ สำหรับงานเรียงที่ดี	เมิร์จซอร์ต
O(n^2)	โตเร็ว	ลูปซ้อนสองชั้น
O(2^n)	พุ่งแรงมาก	แตกกิ่ง recursion แบบไม่เก็บผล

Data Structures & Algorithms

1. Big-O notation คืออะไร

2. ทำไมเราต้องวิเคราะห์ประสิทธิภาพของอัลกอริทึม

3. Big-O บอกอะไร และไม่ได้บอกอะไร

4. ตัวอย่างจากชีวิตจริง

5. แนวคิดเรื่อง input size

6. แนวคิดเรื่องอัตราการเติบโต (growth rate)

7. ทำไมละค่าคงที่ได้

8. ทำไมสนใจพจน์ที่โตเร็วที่สุด

9. ตัวอย่าง Big-O พื้นฐาน

10. ตัวอย่างโค้ด JavaScript ของแต่ละแบบ พร้อมวิเคราะห์ทีละขั้น

O(1) - อ่านสมาชิกตำแหน่งที่กำหนด

O(log n) - ค้นหาแบบหารครึ่ง

O(n) - เดินผ่านข้อมูลหนึ่งรอบ

O(n log n) - ผสมการแบ่งครึ่ง + รวมผล

O(n^2) - ลูปซ้อนสองชั้น

O(2^n) - เรียกซ้ำแตกกิ่ง

11. วิธีดู Big-O จาก loop เดี่ยว

12. วิธีดู Big-O จาก nested loop

13. วิธีดู Big-O จากการหารครึ่งข้อมูล

14. ข้อผิดพลาดที่พบบ่อย

15. สรุปเปรียบเทียบ Big-O แต่ละแบบ

16. สรุปท้ายบทแบบจำง่าย

17. แบบฝึกหัด 4 ข้อ พร้อมแนวเฉลย

ข้อ 1ฟังก์ชันอ่านค่า `items[0]` แล้วคืนค่า มี Big-O เท่าไรกดเพื่อดูแนวเฉลย

ข้อ 2มีลูปเดี่ยววิ่งครบทุกสมาชิกของอาเรย์ 1 รอบ Big-O คืออะไรกดเพื่อดูแนวเฉลย

ข้อ 3มีลูปซ้อน 2 ชั้น โดยแต่ละชั้นวิ่งใกล้เคียง n รอบ Big-O คืออะไรกดเพื่อดูแนวเฉลย

ข้อ 4อัลกอริทึมหนึ่งมีสมการ T(n) = 5n^2 + 8n + 100 ถามว่า Big-O เท่าไรกดเพื่อดูแนวเฉลย

ภาพประกอบการเติบโต

Loading

Data Structures & Algorithms

1. Big-O notation คืออะไร

2. ทำไมเราต้องวิเคราะห์ประสิทธิภาพของอัลกอริทึม

3. Big-O บอกอะไร และไม่ได้บอกอะไร

4. ตัวอย่างจากชีวิตจริง

5. แนวคิดเรื่อง input size

6. แนวคิดเรื่องอัตราการเติบโต (growth rate)

7. ทำไมละค่าคงที่ได้

8. ทำไมสนใจพจน์ที่โตเร็วที่สุด

9. ตัวอย่าง Big-O พื้นฐาน

10. ตัวอย่างโค้ด JavaScript ของแต่ละแบบ พร้อมวิเคราะห์ทีละขั้น

O(1) - อ่านสมาชิกตำแหน่งที่กำหนด

O(log n) - ค้นหาแบบหารครึ่ง

O(n) - เดินผ่านข้อมูลหนึ่งรอบ

O(n log n) - ผสมการแบ่งครึ่ง + รวมผล

O(n^2) - ลูปซ้อนสองชั้น

O(2^n) - เรียกซ้ำแตกกิ่ง

11. วิธีดู Big-O จาก loop เดี่ยว

12. วิธีดู Big-O จาก nested loop

13. วิธีดู Big-O จากการหารครึ่งข้อมูล

14. ข้อผิดพลาดที่พบบ่อย

15. สรุปเปรียบเทียบ Big-O แต่ละแบบ

16. สรุปท้ายบทแบบจำง่าย

17. แบบฝึกหัด 4 ข้อ พร้อมแนวเฉลย

ข้อ 1ฟังก์ชันอ่านค่า `items[0]` แล้วคืนค่า มี Big-O เท่าไรกดเพื่อดูแนวเฉลย

ข้อ 2มีลูปเดี่ยววิ่งครบทุกสมาชิกของอาเรย์ 1 รอบ Big-O คืออะไรกดเพื่อดูแนวเฉลย

ข้อ 3มีลูปซ้อน 2 ชั้น โดยแต่ละชั้นวิ่งใกล้เคียง n รอบ Big-O คืออะไรกดเพื่อดูแนวเฉลย

ข้อ 4อัลกอริทึมหนึ่งมีสมการ T(n) = 5n^2 + 8n + 100 ถามว่า Big-O เท่าไรกดเพื่อดูแนวเฉลย

ภาพประกอบการเติบโต