Time & Space

Time Complexity คืออะไร

**Time Complexity** คือวิธีการวัดว่า **Algorithm ใช้เวลาเพิ่มขึ้นเท่าไหร่เมื่อ Input Size (n) ใหญ่ขึ้น** — เราไม่ได้วัดเป็นวินาที แต่ **วัดเป็นจำนวน Operation (ขั้นตอนการทำงาน)** **ทำไมถึงไม่วัดเป็นวินาที?** - เวลาจริงขึ้นอยู่กับ CPU, RAM, ภาษา, และ workload ของเครื่อง - เครื่องต่างกัน เวลาก็ต่างกัน แต่อัตราการเติบโตของ algorithm ไม่เปลี่ยน **Big-O Notation** เป็นเครื่องมือที่ใช้บอก Time Complexity โดยอธิบายว่าเมื่อ n ใหญ่ขึ้นมากๆ จำนวน Operation จะโตตามสมการอะไร **อุปมาอุปไมย:** - การนับ Time Complexity ก็เหมือน **นับจำนวนก้าว** ที่ต้องเดิน ไม่ใช่นับเวลาเป็นนาที - ถ้าบ้านอยู่ 10 ก้าว O(1) คือหยิบของที่อยู่ตรงหน้า, O(n) คือเดินไปเปิดประตูทีละห้อง, O(n²) คือจับคู่ตรวจสอบทุกคู่ของห้องในบ้าน

วิธีนับ Operations

การนับ Operations เริ่มจากง่ายที่สุด: **นับทีละบรรทัดหรือคำสั่ง** — assignment = 1 operation, comparison = 1 operation, loop body = จำนวนรอบ × จำนวน operation ใน loop **กฎเบื้องต้น:** - `return`, `let x = 1`, `arr[0]` = 1 operation - `if`, `===`, `+`, `-` = 1 operation - `for (let i=0; i<n; i++)` = loop body × n ครั้ง

function getFirst(arr) {
  return arr[0]; // 1 operation — ไม่ว่า arr จะใหญ่แค่ไหน ก็ทำครั้งเดียว
}

// O(1) — Constant Time

function sum(arr) {
  let total = 0;            // 1 operation — init

  for (let i = 0; i < arr.length; i++) {
    total += arr[i];        // n operations — 1 per element
  }

  return total;             // 1 operation — return
}

// รวม: 1 + n + 1 = n + 2 ≈ O(n)
// เราสนใจแค่ growth rate — ค่าคงที่ (2) ถูกตัดทิ้ง

**ข้อสังเกตสำคัญ:** เราไม่ได้สนใจจำนวนเป๊ะๆ แต่สนใจว่า **เมื่อ n ใหญ่ขึ้นมากๆ โค้ดจะช้าลงในอัตราเท่าไหร่** - ถ้า n = 1,000 → O(n) = ~1,000 operations, O(n²) = ~1,000,000 operations - ถ้า n = 1,000,000 → O(n) = ~1,000,000 operations, O(n²) = ~1,000,000,000,000 operations ค่าคงที่ (เช่น +2, ×3) ไม่มีผลเมื่อ n ใหญ่พอ — นี่คือหัวใจของ Asymptotic Analysis

Growth Rate กับขนาด Input

ตารางด้านล่างแสดงให้เห็นว่า **Big-O แต่ละคลาสมีการเติบโตที่แตกต่างกันมาก** เมื่อ n เพิ่มจาก 10 เป็น 1,000,000: - **O(1)** — ไม่เปลี่ยนเลย ไม่ว่า n จะใหญ่แค่ไหน - **O(log n)** — โตช้ามาก (binary search ใน 1 ล้านรายการ ใช้แค่ ~20 ครั้ง) - **O(n)** — โตตาม n ตรงๆ (linear) - **O(n²)** — โตไวมาก input แสนรายการ = หมื่นล้าน operations - **O(2ⁿ)** — ระเบิด exponential n > 30 ก็แทบรันไม่ไหว

• **O(1) — Constant** `n = 10 → 1 operation` `n = 1,000,000 → 1 operation` ไม่เปลี่ยนเลย — เร็วที่สุด ไม่มีอะไรดีกว่านี้
• **O(log n) — Logarithmic** `n = 10 → ~4 operations` `n = 1,000,000 → ~20 operations` โตช้ามาก — binary search, divide & conquer
• **O(n) — Linear** `n = 10 → 10 operations` `n = 1,000,000 → 1,000,000 operations` โตตาม n ตรงๆ — loop เดียว
• **O(n²) — Quadratic** `n = 10 → 100 operations` `n = 1,000,000 → 1,000,000,000,000 operations` โตตาม n² — nested loop สองชั้น
• **O(2ⁿ) — Exponential** `n = 10 → 1,024 operations` `n = 20 → 1,048,576 operations` `n = 30 → ~1,000,000,000 operations` โตระเบิด — ใช้ได้แค่ n น้อยมาก

Best / Average / Worst Case

Algorithm มีสามกรณีที่ต้องพิจารณา: 1. **Best Case (กรณีดีที่สุด)** — จำนวน operations น้อยที่สุดที่อาจเกิดได้ 2. **Average Case (กรณีเฉลี่ย)** — จำนวน operations โดยเฉลี่ยจาก input ที่เป็นไปได้ทั้งหมด 3. **Worst Case (กรณีแย่ที่สุด)** — จำนวน operations มากที่สุดที่อาจเกิดได้ **(นี่คือสิ่งที่ Big-O ใช้วิเคราะห์)** **ทำไมต้องสนใจ Worst Case?** - Worst case คือ **การันตี** ว่า algorithm จะไม่ช้ากว่านี้ ไม่ว่าอะไรจะเกิดขึ้น - Best case มักจะเป็น O(1) แต่ไม่ได้ช่วยให้เราวางแผนระบบสำหรับ input ใหญ่ๆ ได้

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      return i; // เจอแล้ว → จบ
    }
  }
  return -1; // ไม่เจอเลย
}

// Best Case:  O(1) — target อยู่ที่ arr[0]
// Average Case: O(n) — target อยู่ตรงกลาง (n/2 ≈ O(n))
// Worst Case: O(n) — target อยู่ตำแหน่งสุดท้าย หรือไม่มีเลย

// Big-O ของ linearSearch = O(n)
// เพราะ worst case คือ scan ทั้งอาเรย์

**กฎ:** เวลาพูดถึง Big-O โดยไม่ระบุว่า best/average/worst → **หมายถึง Worst Case เสมอ** เพราะเราอยากรู้ว่า algorithm จะแย่สุดขนาดไหน

Asymptotic Analysis — การ Simplify

การวิเคราะห์แบบ Asymptotic คือการดูว่า **เมื่อ n เข้าใกล้ infinity (→∞) พจน์ไหนจะ dominate** มากที่สุด **กฎ 3 ข้อในการ Simplify Big-O:** 1. **Drop Constants (ตัดค่าคงที่):** `O(2n) → O(n)`, `O(100) → O(1)`, `O(n/2) → O(n)` 2. **Drop Lower-Order Terms (ตัดพจน์ที่โตช้ากว่า):** `O(n² + n) → O(n²)`, `O(n + log n) → O(n)` 3. **Keep Only Dominant Term (เก็บเฉพาะพจน์ที่โตเร็วที่สุด):** `O(n³ + n² + n + 1) → O(n³)`

function process(arr) {
  console.log(arr[0]);      // O(1)

  for (let i = 0; i < arr.length; i++) {       // O(n)
    for (let j = 0; j < arr.length; j++) {     // O(n²)
      console.log(i, j);
    }
  }
}

// Total: O(1) + O(n) + O(n²)
// ตัดค่าคงที่ + ตัด lower-order → O(n²)

// O(n²) ใหญ่กว่า O(n) และ O(1) มากๆ เมื่อ n ใหญ่
// เลย dominate ทุกอย่าง

**ทำไมต้องตัดค่าคงที่?** — สมมุติ O(2n) กับ O(n²): - n=10 → 2n=20, n²=100 → n² ช้ากว่า - n=1000 → 2n=2000, n²=1,000,000 → n² ช้ากว่า 500 เท่า! ค่าคงที่ 2 ไม่สำคัญเลยเมื่อ n ใหญ่พอ — การเติบโตแบบ n² จะกลบทุกอย่าง

วิเคราะห์ Nested Loops

Nested Loop เป็น pattern ที่พบบ่อยมาก หลักการวิเคราะห์คือ **คูณ (Multiply)** จำนวนรอบของแต่ละ loop: - **Loop เดียว (Single Loop):** `for i 0..n` = O(n) - **Nested Loop สองชั้น (Double Nested):** `for i 0..n` ข้างในมี `for j 0..n` = O(n × n) = O(n²) - **Nested Loop สามชั้น (Triple Nested):** O(n × n × n) = O(n³) **กรณี Array คนละขนาด:** ถ้า loop นึงวน `arr1` อีก loop วน `arr2` → O(n × m) — ใช้ตัวแปรคนละตัวกัน

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {       // n รอบ
    for (let j = 0; j < arr.length - i - 1; j++) { // ~n/2 รอบโดยเฉลี่ย
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// outer loop: n, inner loop: ~n/2 → n × n/2 = n²/2 → O(n²)

function crossMatch(arr1, arr2) {
  const result = [];
  for (let i = 0; i < arr1.length; i++) {       // n รอบ
    for (let j = 0; j < arr2.length; j++) {     // m รอบ
      if (arr1[i] === arr2[j]) {
        result.push(arr1[i]);
      }
    }
  }
  return result;
}

// n = arr1.length, m = arr2.length
// Time Complexity: O(n × m)
// ถ้า n ≈ m → O(n²)

วิเคราะห์ Divide & Conquer — O(n log n)

**Divide & Conquer** คือการแบ่งปัญหาเป็นส่วนย่อย แก้ส่วนย่อย แล้วรวมผลลัพธ์กลับ **ทำไมถึงเป็น O(n log n)?** - **log n** มาจากการแบ่งครึ่งซ้ำๆ — ต้องแบ่งกี่ครั้งถึงจะเหลือขนาด 1? = log₂(n) ครั้ง - **n** มาจากการประมวลผลข้อมูลทั้งหมดในแต่ละระดับ — merge step ต้องรวมข้อมูลทั้งหมด - รวมกัน: **log n ระดับ × n operations ต่อระดับ = O(n log n)** ตัวอย่าง: **Merge Sort** และ **Quick Sort (average case)** มี Time Complexity = O(n log n)

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

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // แบ่งซ้าย → log n depth
  const right = mergeSort(arr.slice(mid));      // แบ่งขวา → log n depth

  return merge(left, right);                     // O(n) per level
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) { // O(n) รวม
    if (left[i] < right[j]) result.push(left[i++]);
    else result.push(right[j++]);
  }
  return [...result, ...left.slice(i), ...right.slice(j)];
}

// แต่ละ level ใช้ O(n) รวมกัน
// มีทั้งหมด log₂(n) levels
// → O(n log n)

วิเคราะห์ Recursion

การวิเคราะห์ Recursive Function ต้องดูสองอย่าง: 1. **จำนวนครั้งที่ฟังก์ชันเรียกตัวเอง (Branching Factor)** — เรียกกี่ครั้งต่อหนึ่ง call 2. **ความลึกของการเรียกซ้ำ (Recursion Depth)** — เรียกซ้อนกันลึกแค่ไหน **รวมกัน:** Time Complexity = O(branchingFactor ^ depth) สำหรับ full recursion tree

function fib(n) {
  if (n <= 1) return n;  // base case
  return fib(n - 1) + fib(n - 2); // แยกเป็น 2 ทาง — 2 branching
}

// แต่ละ call แยกเป็น 2 subcall (branching factor = 2)
// ความลึกของ call tree = n
// → จำนวน call ทั้งหมด ≈ 2ⁿ

// fib(5): 15 calls
// fib(10): 177 calls
// fib(20): 21,891 calls
// fib(50): ~2²⁵ trillion calls — รันไม่ไหว!

**Exponential O(2ⁿ) เป็นหนึ่งในรูปแบบที่แย่ที่สุด** — ใช้ได้กับ n น้อยๆ เท่านั้น (n ≤ 20-30) ทางแก้คือใช้ **Memoization** หรือเปลี่ยนเป็น iterative loop (O(n)) **Recursion อื่นๆ:** - Binary Search (recursive): แบ่งครึ่งทีละข้าง → O(log n) - Tree Traversal (ทุก node): ผ่านทุก node ครั้งเดียว → O(n) - Merge Sort (recursive): แบ่งครึ่ง + รวม → O(n log n)

กฎสำคัญในการวิเคราะห์ Time Complexity

สรุป: Time Complexity Cheat Sheet

**Cheat Sheet นี้เป็นแนวทางเบื้องต้นในการวิเคราะห์ Time Complexity** — จำไว้ว่า: - **Loop เดียว = O(n)**, **Nested Loop = คูณกัน**, **Divide by 2 = O(log n)** - **Recursion ต้องดู branching factor × depth** - **ตัดค่าคงที่กับ lower-order term แล้วเก็บเฉพาะ dominant term** - **Big-O = Worst Case** (ยกเว้นระบุเป็นอย่างอื่น) - **Space มักถูกละเลยน้อยกว่า แต่สำคัญไม่แพ้ Time ในการตัดสินใจเลือก Algorithm**

ทบทวนความเข้าใจ: Time Complexity