Time & Space

Space Complexity คืออะไร

**Space Complexity** คือการวัดปริมาณ **หน่วยความจำ (memory)** ทั้งหมดที่ algorithm ใช้ เทียบกับขนาด input (n) ประกอบด้วย 2 ส่วนหลัก: 1. **Input Space** — หน่วยความจำที่ใช้เก็บข้อมูล input ที่ส่งเข้ามา (เช่น อาเรย์ขนาด n) 2. **Auxiliary Space** — หน่วยความจำ **เพิ่มเติม** ที่สร้างระหว่างการคำนวณ (เช่น ตัวแปร, อาเรย์ใหม่, recursion call stack) การวิเคราะห์ Space Complexity ใช้หลักการเดียวกับ Time Complexity — ตัดค่าคงที่ (constants) และเก็บเฉพาะ dominant term **ตัวอย่าง:** - ฟังก์ชันที่รับอาเรย์ขนาด n และสร้างตัวแปร 1 ตัว → ใช้ O(1) auxiliary space - ฟังก์ชันที่รับอาเรย์ขนาด n และสร้างอาเรย์ใหม่ขนาด n → ใช้ O(n) auxiliary space - ฟังก์ชันที่สร้าง matrix ขนาด n×n → ใช้ O(n²) auxiliary space

Input Space vs Auxiliary Space

ในการวิเคราะห์ Space Complexity โดยทั่วไปเรา **ไม่นับ Input Space** (เพราะเป็นข้อมูลที่ได้รับมาอยู่แล้ว) แต่ **นับ Auxiliary Space** (เพราะเป็นส่วนที่เราสร้างเพิ่ม) **ตัวอย่างเปรียบเทียบ:** - Two Sum Brute Force → ใช้แค่ loop variables → O(1) auxiliary - Two Sum Hash Map → สร้าง `seen` object ขนาด n → O(n) auxiliary **ข้อควรจำ:** ถ้าโจทย์ระบุว่านับรวม input space ด้วย ให้บอกว่า total space = input + auxiliary

function twoSumBruteForce(nums, target) {
  // ไม่สร้าง data structure ใหม่
  // ใช้แค่ตัวแปร i, j → O(1) auxiliary space
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [-1, -1];
}

function twoSumHash(nums, target) {
  const seen = {}; // ← สร้าง object ใหม่!
  // object นี้สามารถโตได้ถึงขนาด n → O(n) auxiliary space

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen[complement] !== undefined) {
      return [seen[complement], i];
    }
    seen[nums[i]] = i;
  }
  return [-1, -1];
}

**Total Space = Input Space + Auxiliary Space** ปกติเราวิเคราะห์ Auxiliary Space แยกต่างหาก เพราะ input space ถูกกำหนดโดยโจทย์อยู่แล้ว สิ่งที่เราควบคุมได้คือ auxiliary space — พื้นที่ที่เราสร้างเพิ่มเอง

O(1) Extra Space — In-place Algorithms

**In-place Algorithm** คืออัลกอริทึมที่แก้ไขข้อมูลใน input โดยตรง โดย **ไม่สร้างข้อมูลใหม่ที่มีขนาด proportional กับ n** ใช้ auxiliary space เพียง O(1) — แค่ตัวแปรชั่วคราว **ตัวอย่าง In-place:** - Reverse array by swapping - Bubble Sort - Insertion Sort - Selection Sort **ตัวอย่าง NOT In-place:** - Merge Sort (ต้องสร้าง array ย่อย) - Filter ที่สร้าง array ใหม่

function reverseInPlace(arr) {
  let left = 0;
  let right = arr.length - 1;
  while (left < right) {
    [arr[left], arr[right]] = [arr[right], arr[left]];
    left++;
    right--;
  }
  return arr;
}

ใช้แค่ 2 ตัวแปร (`left`, `right`) ไม่ว่าอาเรย์จะใหญ่แค่ไหน → O(1) auxiliary space หลักการ: เราเปลี่ยนลำดับข้อมูลในอาเรย์เดิมโดยตรง โดยใช้ pointer สองตัวสลับค่าจากขอบเข้ามาตรงกลาง

O(n) Extra Space — ใช้โครงสร้างข้อมูลเพิ่ม

เมื่อเราต้องการเก็บผลลัพธ์หรือข้อมูลระหว่างทางที่ขนาดขึ้นอยู่กับ input n → auxiliary space = O(n) **ตัวอย่างที่ใช้ O(n) auxiliary:** - `filter()` → สร้างอาเรย์ใหม่เก็บค่าที่ผ่านเงื่อนไข - Hash Map / Object → เก็บข้อมูลเพื่อ lookup - `Array.from()` / Spread operator → คัดลอกอาเรย์ ไม่ใช่เรื่องแย่ — บางครั้งการใช้ O(n) space เพื่อให้ได้ O(n) time เป็น trade-off ที่สมเหตุสมผล

function filterEven(arr) {
  const result = []; // ← อาเรย์นี้โตได้ถึง n
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] % 2 === 0) {
      result.push(arr[i]);
    }
  }
  return result; // worst case: ทุกตัวเป็นเลขคู่ → result มี n ตัว
}

function getUniqueValues(arr) {
  const seen = new Set();  // ← O(n) auxiliary
  const result = [];       // ← O(n) auxiliary (worst case)

  for (let i = 0; i < arr.length; i++) {
    if (!seen.has(arr[i])) {
      seen.add(arr[i]);
      result.push(arr[i]);
    }
  }
  return result;
}

Space Complexity ของ Recursion

Recursion ใช้ **Call Stack** ในการทำงาน — ทุกครั้งที่ฟังก์ชันเรียกตัวเอง recursive call จะถูก push เข้า stack frame ใหม่ **Space = จำนวน stack frames × ขนาดต่อ frame** - Iterative approach → O(1) space (ใช้ loop ปกติ) - Recursive approach → O(depth) space (stack frame สะสม) **สำคัญ:** ถึงแม้จะไม่สร้างตัวแปรเพิ่มภายในฟังก์ชัน recursive แต่ call stack เองก็ใช้หน่วยความจำ!

function sum(arr, n) {
  if (n <= 0) return 0;
  return arr[n - 1] + sum(arr, n - 1);
  // แต่ละ recursive call → เพิ่ม 1 stack frame
  // เรียก n ครั้ง → n frames → O(n) space
}

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;

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

  if (arr[mid] === target) return mid;
  if (arr[mid] > target) {
    return binarySearch(arr, target, left, mid - 1);
  }
  return binarySearch(arr, target, mid + 1, right);
  // แบ่งครึ่งทุกครั้ง → depth = log n → O(log n) space
}

**เปรียบเทียบ:** - Sum แบบ iterative = O(1) space, Sum แบบ recursive = O(n) space - Recursion มักทำให้โค้ดอ่านง่ายขึ้น แต่แลกมาด้วย space ที่เพิ่มขึ้น - Tail-call optimization (TCO) ในบางภาษา (ไม่ใช่ JavaScript ทุก environment) ช่วยลด stack frames ให้เหลือ O(1) ได้

Time-Space Trade-off

**Time-Space Trade-off** คือหลักการที่ว่า algorithm ส่วนใหญ่สามารถ **แลก space กับ time** — ทำให้เร็วขึ้นด้วยการใช้ memory มากขึ้น หรือประหยัด memory โดยยอมใช้เวลามากขึ้น ไม่มี algorithm ไหนดีที่สุดในทุกมิติ — คำถามคือ **คุณมีทรัพยากรอะไรเหลือเฟือ?**

**คำถามสำคัญเมื่อต้องเลือก algorithm: คุณมีเวลาเยอะหรือมี memory เยอะ?** - **Memory เพียงพอ** → ใช้ hash map / memoization — ลดเวลา - **Memory จำกัด** (embedded, mobile) → ใช้ in-place — ลด space - **n น้อย** → ไม่ต้อง optimize เลย คำนวณเร็วพออยู่แล้ว - **n ใหญ่มาก** → ต้อง optimize time ก่อน (ถ้า memory พอ)

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

สรุป: Space Complexity Cheat Sheet

**Rule of thumb:** - ถ้าไม่สร้าง array/object ใหม่ที่ขนาดขึ้นกับ n → O(1) - ถ้าสร้าง → ดูว่าขนาดเท่าไหร่ - 1D proportional to n → O(n) - 2D (n×m) → O(n×m) หรือ O(n²) - Recursion depth → O(depth)

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