Array-a01

02Learn

บทเรียน

Array-a

Big-O Notation

O(log n) — Logarithmic Time

เรียนรู้ O(log n) Logarithmic Time — operations ที่ตัดข้อมูลทิ้งครึ่งหนึ่งทุกขั้นตอน พร้อม 6 Labs ฝึกเขียน halving, number guessing, boundary search, doubling, power of 2, และ binary search

O(log n) คืออะไร

O(log n) หรือ **Logarithmic Time** หมายความว่า ทุกขั้นตอนจะ **ตัดข้อมูลทิ้งครึ่งหนึ่ง** — ทำให้จำนวนขั้นตอนเติบโตช้ามาก แม้ n จะใหญ่ขึ้นมาก

O(log n) — ตัดครึ่งซ้ำๆJS

// นับว่าต้องหาร n ด้วย 2 กี่ครั้ง จึงจะเหลือ 1
function countHalvings(n) {
  let steps = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    steps++;
  }
  return steps;
}

console.log(countHalvings(8));     // 3   (8 → 4 → 2 → 1)
console.log(countHalvings(1024));  // 10
console.log(countHalvings(1000000)); // 19

ลองนึกภาพ: คุณมีหนังสือพจนานุกรม 1,000 หน้า และต้องหาคำว่า "mongoose" คุณไม่ไล่หน้าทีละหน้า (นั่นคือ O(n)) แต่เปิดกลางเล่มก่อน ดูว่าคำที่หาอยู่ก่อนหรือหลังจุดนั้น แล้วตัดครึ่งที่ไม่เกี่ยวทิ้ง — ทำซ้ำจนเจอ นี่คือ O(log n)

ทำไม log₂(n) ถึงเติบโตช้ามาก

เพราะทุกรอบตัดทิ้งครึ่งหนึ่ง จำนวนขั้นตอนจึงเป็น **logarithm base 2** ของ n — คือ 2 ยกกำลังเท่าไหร่จึงจะได้ n

n (ขนาดข้อมูล)	log₂(n) (จำนวนขั้นตอน)	เปรียบเทียบ
10	~3	3 รอบ
100	~7	7 รอบ
1,000	~10	10 รอบ
1,000,000	~20	แค่ 20 รอบ!
1,000,000,000	~30	แค่ 30 รอบ!

สังเกต: เมื่อ n เพิ่ม 1,000 เท่า (จาก 1,000 เป็น 1,000,000) จำนวนขั้นตอนเพิ่มแค่ 10 (จาก 10 เป็น 20) — นี่คือพลังของ O(log n)

ตัวอย่าง O(log n): การตัดครึ่งซ้ำๆ

รูปแบบที่พบบ่อยที่สุดของ O(log n) คือ **การวนลูปที่ทุกรอบลดขนาดปัญหาลงครึ่งหนึ่ง** — เช่น หารด้วย 2, ย้ายขอบเขตซ้าย/ขวา, หรือข้ามไปครึ่งทาง

Halving loop — O(log n)JS

// ลดค่าลงครึ่งหนึ่งทุกรอบ
function halve(n) {
  let steps = 0;
  while (n > 1) {
    n = Math.floor(n / 2);
    steps++;
  }
  return steps;
}

// ข้อมูล 100,000 ตัว → แค่ 16 รอบ
console.log(halve(100000)); // 16

กฎง่ายๆ: **ถ้าทุกรอบของ loop ลดขนาดข้อมูลลงคงที่ (เช่น ครึ่งหนึ่ง) นั่นคือ O(log n)**

ตัวอย่าง O(log n): ค้นหาในข้อมูลที่เรียงแล้ว

เมื่อข้อมูล **เรียงลำดับแล้ว** เราสามารถตรวจจุดกลางแล้วตัดครึ่งทิ้งได้เลย — ไม่ต้องไล่ดูทุกตัว เทคนิคนี้เรียกว่า binary search

Binary search concept — O(log n)JS

const sorted = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91];

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

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

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

  return false;
}

console.log(binaryContains(sorted, 23));  // true
console.log(binaryContains(sorted, 7));   // false

ทุกรอบของ while loop ตัดช่วงค้นหาทิ้งครึ่งหนึ่ง (ย้าย left หรือ right) ทำให้จำนวนรอบ = log₂(n) — เราจะเจาะจง binary search เพิ่มเติมในบทเรียนถัดไปของ phase Searching

สิ่งที่ ไม่ใช่ O(log n)

เข้าใจผิดบ่อยที่สุดคือ คิดว่า loop ที่ใช้ / 2 ทุกรอบเป็น O(log n) เสมอ ความจริงคือ **ถ้า loop ไม่ได้ลดขนาดปัญหาลงอย่างก้าวหน้า มันไม่ใช่ O(log n)**

ตัวอย่างที่ไม่ใช่ O(log n)JS

// ❌ ไล่ทุกตัว — O(n)
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

// ❌ ซ้อนกัน — O(n²)
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    console.log(arr[i], arr[j]);
  }
}

// ❌ หารด้วย 2 แต่ loop ไม่ได้ลดขนาด — O(n)
// (ตัวแปร i หาร 2 แต่ arr ไม่ได้ลดขนาด)
for (let i = arr.length; i > 0; i = Math.floor(i / 2)) {
  console.log(arr[i]); // นี่คือ O(log n) ถ้าดูแค่ i
}

กฎง่ายๆ: **O(log n) ต้องมีการ "ตัดทิ้ง" ส่วนของข้อมูลอย่างก้าวหน้าทุกรอบ** — ถ้าทุกรอบยังต้องดูข้อมูลทั้งหมด นั่นคือ O(n) หรือมากกว่า

กฎสำคัญ: O(log n) Patterns