Fundamentalsบทที่ 2Time vs Space Complexity

เวลา vs หน่วยความจำ: เข้าใจ trade-off แบบใช้งานจริง

บทนี้จะพาเรียนทีละขั้นว่า เวลาในการทำงาน (Time Complexity) และการใช้หน่วยความจำ (Space Complexity) คืออะไร ต่างกันอย่างไร และเราควรตัดสินใจเลือกอัลกอริทึมแบบไหนเมื่อเจอข้อจำกัดจริง

1. Time Complexity คืออะไร

เวลาในการทำงาน (Time Complexity) คือการวัดว่าเมื่อขนาดข้อมูล (n) เพิ่มขึ้น จำนวนขั้นตอนที่อัลกอริทึมต้องทำเพิ่มขึ้นอย่างไร

เรามองแนวโน้ม ไม่ได้วัดวินาทีจริงบนเครื่อง เพราะความเร็วเครื่องและระบบรันจริง ต่างกันได้

2. Space Complexity คืออะไร

การใช้หน่วยความจำ (Space Complexity) คือการวัดว่าระหว่างทำงาน อัลกอริทึมต้องขอพื้นที่เพิ่มเติมจากข้อมูลเดิมเท่าไร

เช่น ใช้อาเรย์ใหม่, แฮชแมป (Hash Map), เซต (Set), หรือคอลสแตก (Call Stack) ที่โตตาม n

3. ทำไมต้องวิเคราะห์ทั้งสองอย่าง

ดูแค่เวลาอย่างเดียวไม่พอ

บางวิธีเร็วมากแต่กินหน่วยความจำสูง ถ้าเครื่องมีแรมจำกัดอาจใช้ไม่ได้จริง

ดูแค่หน่วยความจำก็ไม่พอ

บางวิธีประหยัดพื้นที่แต่ช้ามาก เมื่อข้อมูลใหญ่จะกระทบประสบการณ์ใช้งาน

4. ความต่างระหว่างเวลาในการทำงานกับการใช้หน่วยความจำ

ภาพที่ 1: Time Complexity บอกแนวโน้มเวลาทำงาน ส่วน Space Complexity บอกแนวโน้มการใช้หน่วยความจำเพิ่มเติม ทั้งสองมิติควรวิเคราะห์ร่วมกัน

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

เตรียมโน้ตย่อก่อนสอบ

เราใช้เวลาจัดโน้ตเพิ่ม (ใช้ทรัพยากรล่วงหน้า) เพื่อให้ตอนทบทวนเร็วขึ้น

เข้าครัวแบบเตรียมวัตถุดิบล่วงหน้า

การหั่นของเก็บใส่กล่องเพิ่มพื้นที่จัดเก็บ แต่ช่วยให้ทำอาหารตอนจริงเร็วขึ้น

เก็บเบอร์โทรในสมุด vs จำจากประวัติแชต

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

6. อธิบายแนวคิด trade-off

trade-off คือการแลกกันของทรัพยากร: ถ้าอยากได้อย่างหนึ่งมากขึ้น มักต้องยอมเสียอีกอย่างหนึ่ง เช่น เร็วขึ้นแต่ใช้หน่วยความจำเพิ่ม หรือประหยัดหน่วยความจำแต่ช้าลง

เป้าหมายจึงไม่ใช่หาอัลกอริทึมที่ดีที่สุดตลอดกาล แต่หาอัลกอริทึมที่ "เหมาะกับบริบท" มากที่สุด

ภาพที่ 2: trade-off คือการแลกทรัพยากร เราอาจยอมใช้หน่วยความจำเพิ่มเพื่อให้เร็วขึ้น หรือยอมช้าลงเพื่อประหยัดหน่วยความจำ ขึ้นกับข้อจำกัดของระบบ

7. ตัวอย่างอัลกอริทึมที่ใช้เวลาน้อยแต่ใช้หน่วยความจำมาก

ตัวอย่างคลาสสิกคือใช้แฮชแมป (Hash Map) หรือเซต (Set) ช่วยจำข้อมูลที่เคยเจอ ทำให้ลดเวลาค้นหาซ้ำ แต่ต้องใช้พื้นที่เพิ่มตามขนาดข้อมูล

8. ตัวอย่างอัลกอริทึมที่ใช้หน่วยความจำน้อยแต่ใช้เวลามาก

วิธีที่ไม่เก็บข้อมูลช่วย เช่น ลูปซ้อนเทียบทุกคู่ มักใช้พื้นที่น้อย แต่จำนวนขั้นตอนเยอะกว่าเมื่อข้อมูลใหญ่

Lab (ก่อนหัวข้อ 9): ลองทำ Two Sum แล้วดูเวลาเทียบกัน

ลองทำโจทย์นี้ก่อน แล้วค่อยเลื่อนลงไปอ่านหัวข้อ 9 เพื่อเชื่อมแนวคิด Trade-off ให้ชัดขึ้น: คุณจะเห็นว่าโค้ดที่ใช้หน่วยความจำเพิ่ม สามารถทำให้เวลาลดลงได้จริงในหลายกรณี

Lab นี้ตรวจอย่างไร

ตัวตรวจจะเช็กทั้งกรณีพบคำตอบ, ไม่พบคำตอบ, เจอที่ตำแหน่งต้นลิสต์ และค่าติดลบ โดยตรวจแยกทั้งสองฟังก์ชัน เพื่อยืนยันว่าคืนค่าถูกต้องก่อนดูผลเปรียบเทียบเวลา

Learning Lab

Warm-up Lab: Two Sum (เริ่มจากศูนย์)

โจทย์คือ: รับอาเรย์ตัวเลข `nums` และค่า `target` แล้วหาดัชนีของตัวเลข 2 ตัวที่บวกกันได้ `target` (เช่น [2, 7, 11, 15] กับ target = 9 ต้องได้ [0, 1]). ถ้าไม่พบให้คืน `null` จากนั้นลองทำ 2 วิธี (`twoSumBruteForce`, `twoSumHashMap`) เพื่อเปรียบเทียบเวลา

Loading editor surface...

Progress check

Run the preview, then use Run Assessment to evaluate the current result.

Runtime Console

No runtime issues from the current preview.

9. ตัวอย่างโค้ด JavaScript พร้อมวิเคราะห์ Time และ Space

ตัวอย่างหลัก: Two Sum

หาเลข 2 ตัวที่บวกกันได้ค่าเป้าหมาย (target)

วิธี A: Brute Force (ประหยัดพื้นที่แต่ช้ากว่า)

Code AJS

แนวทางที่ใช้หน่วยความจำน้อยกว่า

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i += 1) {
    for (let j = i + 1; j < nums.length; j += 1) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return null;
}

Time Complexity: O(n^2) เพราะมีลูปซ้อนสองชั้น
Space Complexity: O(1) ใช้ตัวแปรเพิ่มเพียงเล็กน้อย
ข้อดี: ประหยัดหน่วยความจำ
ข้อเสีย: ช้าลงมากเมื่อข้อมูลใหญ่

วิธี B: Hash Map (เร็วกว่าแต่ใช้พื้นที่เพิ่ม)

Code BJS

แนวทางที่เร็วกว่าแต่ใช้หน่วยความจำเพิ่ม

function twoSumHashMap(nums, target) {
  const seen = new Map();

  for (let i = 0; i < nums.length; i += 1) {
    const need = target - nums[i];

    if (seen.has(need)) {
      return [seen.get(need), i];
    }

    seen.set(nums[i], i);
  }

  return null;
}

Time Complexity: O(n) เพราะวนลูปเดียว และค้นหาในแฮชแมป (Hash Map) เฉลี่ย O(1)
Space Complexity: O(n) เพราะต้องเก็บข้อมูลที่เจอไว้ในแฮชแมป
ข้อดี: เร็วขึ้นชัดเจนเมื่อข้อมูลเยอะ
ข้อเสีย: ใช้หน่วยความจำเพิ่ม

ตัวอย่างเสริม: ตรวจข้อมูลซ้ำ

เช็กว่าในลิสต์มีข้อมูลซ้ำหรือไม่

วิธี A: ลูปซ้อนเทียบทุกคู่ (พื้นที่น้อยแต่ช้ากว่า)

Code AJS

แนวทางที่ใช้หน่วยความจำน้อยกว่า

function hasDuplicateNested(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;
}

Time Complexity: O(n^2) จากลูปซ้อน
Space Complexity: O(1) ไม่ใช้โครงสร้างข้อมูลขนาดใหญ่เพิ่ม
ข้อดี: ใช้เมมโมรีน้อย
ข้อเสีย: ช้าเมื่อข้อมูลมีจำนวนมาก

วิธี B: ใช้เซต (Set) ช่วยจำ (เร็วกว่าแต่พื้นที่มากกว่า)

Code BJS

แนวทางที่เร็วกว่าแต่ใช้หน่วยความจำเพิ่ม

function hasDuplicateSet(items) {
  const seen = new Set();

  for (const item of items) {
    if (seen.has(item)) {
      return true;
    }

    seen.add(item);
  }

  return false;
}

Time Complexity: O(n) เพราะเดินข้อมูลหนึ่งรอบ
Space Complexity: O(n) เพราะเซตเก็บสมาชิกที่เคยเห็น
ข้อดี: เร็วและอ่านง่าย
ข้อเสีย: ใช้หน่วยความจำตามขนาดข้อมูล

10. กรณีที่ควรสนใจ Time มากกว่า

ระบบตอบสนองทันที

เช่น ระบบค้นหา, ระบบแชต, หน้าเว็บที่ผู้ใช้รอผลแบบเรียลไทม์

งานที่รันซ้ำบ่อยมาก

ถ้ารันบ่อย การลดเวลาแม้เล็กน้อยต่อครั้งจะช่วยมากในภาพรวม

11. กรณีที่ควรสนใจ Space มากกว่า

เครื่องทรัพยากรจำกัด

เช่น อุปกรณ์พกพา, อุปกรณ์ฝังตัว, หรือคอนเทนเนอร์ที่จำกัดแรม

ข้อมูลใหญ่มากในหน่วยความจำ

ถ้าโครงสร้างช่วยจำโตตามข้อมูล อาจชนข้อจำกัดแรมก่อนเวลาทำงานเสียอีก

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

คิดว่า Time Complexity คือเวลาจริงเป็นวินาทีบนเครื่องเสมอ

ดูแค่ Time Complexity แต่ไม่ดู Space Complexity

คิดว่าใช้หน่วยความจำเพิ่มเป็นเรื่องเสียเสมอ ทั้งที่บางงานต้องการความเร็วมากกว่า

สรุปว่าอัลกอริทึมหนึ่งดีกว่าอีกอันทุกสถานการณ์ โดยไม่ดูบริบทงาน

สับสนว่า Space Complexity นับเฉพาะไฟล์ข้อมูลเดิม ทั้งที่ควรนับหน่วยความจำเพิ่มเติมด้วย

13. ตารางเปรียบเทียบ Time vs Space แบบเข้าใจง่าย

มุมมอง	Time Complexity	Space Complexity
วัดอะไร	จำนวนขั้นตอนการทำงาน	หน่วยความจำเพิ่มเติมที่ใช้
ยิ่งค่าน้อย	ยิ่งตอบเร็วขึ้น	ยิ่งประหยัดเมมโมรี
ตัวอย่างที่พบบ่อย	O(1), O(log n), O(n), O(n^2)	O(1), O(n)
คำถามที่ควรถาม	ช้าไหมเมื่อข้อมูลโต	กินแรมเพิ่มเท่าไรเมื่อข้อมูลโต

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

เวลา (Time) กับหน่วยความจำ (Space) คือทรัพยากรหลักที่ต้องคิดคู่กันเสมอ เมื่อออกแบบอัลกอริทึม

หลักสำคัญคือ trade-off: ไม่มีวิธีเดียวที่ดีที่สุดทุกสถานการณ์ ต้องเลือกตามข้อจำกัดจริงของระบบและเป้าหมายงาน

ถ้าต้องตอบไวมากให้ให้ความสำคัญกับ Time มากขึ้น ถ้าแรมจำกัดมาก ให้ระวัง Space มากขึ้น

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

Fundamentalsบทที่ 2Time vs Space Complexity

เวลา vs หน่วยความจำ: เข้าใจ trade-off แบบใช้งานจริง

1. Time Complexity คืออะไร

2. Space Complexity คืออะไร

เช่น ใช้อาเรย์ใหม่, แฮชแมป (Hash Map), เซต (Set), หรือคอลสแตก (Call Stack) ที่โตตาม n

3. ทำไมต้องวิเคราะห์ทั้งสองอย่าง

ดูแค่เวลาอย่างเดียวไม่พอ

ดูแค่หน่วยความจำก็ไม่พอ

4. ความต่างระหว่างเวลาในการทำงานกับการใช้หน่วยความจำ

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

เตรียมโน้ตย่อก่อนสอบ

เราใช้เวลาจัดโน้ตเพิ่ม (ใช้ทรัพยากรล่วงหน้า) เพื่อให้ตอนทบทวนเร็วขึ้น

เข้าครัวแบบเตรียมวัตถุดิบล่วงหน้า

เก็บเบอร์โทรในสมุด vs จำจากประวัติแชต

6. อธิบายแนวคิด trade-off

7. ตัวอย่างอัลกอริทึมที่ใช้เวลาน้อยแต่ใช้หน่วยความจำมาก

8. ตัวอย่างอัลกอริทึมที่ใช้หน่วยความจำน้อยแต่ใช้เวลามาก

Lab (ก่อนหัวข้อ 9): ลองทำ Two Sum แล้วดูเวลาเทียบกัน

Lab นี้ตรวจอย่างไร

Learning Lab

Warm-up Lab: Two Sum (เริ่มจากศูนย์)

Loading editor surface...

Progress check

Run the preview, then use Run Assessment to evaluate the current result.

Runtime Console

No runtime issues from the current preview.

9. ตัวอย่างโค้ด JavaScript พร้อมวิเคราะห์ Time และ Space

ตัวอย่างหลัก: Two Sum

หาเลข 2 ตัวที่บวกกันได้ค่าเป้าหมาย (target)

วิธี A: Brute Force (ประหยัดพื้นที่แต่ช้ากว่า)

Code AJS

แนวทางที่ใช้หน่วยความจำน้อยกว่า

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i += 1) {
    for (let j = i + 1; j < nums.length; j += 1) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }

  return null;
}

Time Complexity: O(n^2) เพราะมีลูปซ้อนสองชั้น
Space Complexity: O(1) ใช้ตัวแปรเพิ่มเพียงเล็กน้อย
ข้อดี: ประหยัดหน่วยความจำ
ข้อเสีย: ช้าลงมากเมื่อข้อมูลใหญ่

วิธี B: Hash Map (เร็วกว่าแต่ใช้พื้นที่เพิ่ม)

Code BJS

แนวทางที่เร็วกว่าแต่ใช้หน่วยความจำเพิ่ม

function twoSumHashMap(nums, target) {
  const seen = new Map();

  for (let i = 0; i < nums.length; i += 1) {
    const need = target - nums[i];

    if (seen.has(need)) {
      return [seen.get(need), i];
    }

    seen.set(nums[i], i);
  }

  return null;
}

Time Complexity: O(n) เพราะวนลูปเดียว และค้นหาในแฮชแมป (Hash Map) เฉลี่ย O(1)
Space Complexity: O(n) เพราะต้องเก็บข้อมูลที่เจอไว้ในแฮชแมป
ข้อดี: เร็วขึ้นชัดเจนเมื่อข้อมูลเยอะ
ข้อเสีย: ใช้หน่วยความจำเพิ่ม

ตัวอย่างเสริม: ตรวจข้อมูลซ้ำ

เช็กว่าในลิสต์มีข้อมูลซ้ำหรือไม่

วิธี A: ลูปซ้อนเทียบทุกคู่ (พื้นที่น้อยแต่ช้ากว่า)

Code AJS

แนวทางที่ใช้หน่วยความจำน้อยกว่า

function hasDuplicateNested(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;
}

Time Complexity: O(n^2) จากลูปซ้อน
Space Complexity: O(1) ไม่ใช้โครงสร้างข้อมูลขนาดใหญ่เพิ่ม
ข้อดี: ใช้เมมโมรีน้อย
ข้อเสีย: ช้าเมื่อข้อมูลมีจำนวนมาก

วิธี B: ใช้เซต (Set) ช่วยจำ (เร็วกว่าแต่พื้นที่มากกว่า)

Code BJS

แนวทางที่เร็วกว่าแต่ใช้หน่วยความจำเพิ่ม

function hasDuplicateSet(items) {
  const seen = new Set();

  for (const item of items) {
    if (seen.has(item)) {
      return true;
    }

    seen.add(item);
  }

  return false;
}

Time Complexity: O(n) เพราะเดินข้อมูลหนึ่งรอบ
Space Complexity: O(n) เพราะเซตเก็บสมาชิกที่เคยเห็น
ข้อดี: เร็วและอ่านง่าย
ข้อเสีย: ใช้หน่วยความจำตามขนาดข้อมูล

10. กรณีที่ควรสนใจ Time มากกว่า

ระบบตอบสนองทันที

เช่น ระบบค้นหา, ระบบแชต, หน้าเว็บที่ผู้ใช้รอผลแบบเรียลไทม์

งานที่รันซ้ำบ่อยมาก

ถ้ารันบ่อย การลดเวลาแม้เล็กน้อยต่อครั้งจะช่วยมากในภาพรวม

11. กรณีที่ควรสนใจ Space มากกว่า

เครื่องทรัพยากรจำกัด

เช่น อุปกรณ์พกพา, อุปกรณ์ฝังตัว, หรือคอนเทนเนอร์ที่จำกัดแรม

ข้อมูลใหญ่มากในหน่วยความจำ

ถ้าโครงสร้างช่วยจำโตตามข้อมูล อาจชนข้อจำกัดแรมก่อนเวลาทำงานเสียอีก

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

คิดว่า Time Complexity คือเวลาจริงเป็นวินาทีบนเครื่องเสมอ

ดูแค่ Time Complexity แต่ไม่ดู Space Complexity

สรุปว่าอัลกอริทึมหนึ่งดีกว่าอีกอันทุกสถานการณ์ โดยไม่ดูบริบทงาน

13. ตารางเปรียบเทียบ Time vs Space แบบเข้าใจง่าย

มุมมอง	Time Complexity	Space Complexity
วัดอะไร	จำนวนขั้นตอนการทำงาน	หน่วยความจำเพิ่มเติมที่ใช้
ยิ่งค่าน้อย	ยิ่งตอบเร็วขึ้น	ยิ่งประหยัดเมมโมรี
ตัวอย่างที่พบบ่อย	O(1), O(log n), O(n), O(n^2)	O(1), O(n)
คำถามที่ควรถาม	ช้าไหมเมื่อข้อมูลโต	กินแรมเพิ่มเท่าไรเมื่อข้อมูลโต

Data Structures & Algorithms

1. Time Complexity คืออะไร

2. Space Complexity คืออะไร

3. ทำไมต้องวิเคราะห์ทั้งสองอย่าง

4. ความต่างระหว่างเวลาในการทำงานกับการใช้หน่วยความจำ

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

6. อธิบายแนวคิด trade-off

7. ตัวอย่างอัลกอริทึมที่ใช้เวลาน้อยแต่ใช้หน่วยความจำมาก

8. ตัวอย่างอัลกอริทึมที่ใช้หน่วยความจำน้อยแต่ใช้เวลามาก

Lab (ก่อนหัวข้อ 9): ลองทำ Two Sum แล้วดูเวลาเทียบกัน

Warm-up Lab: Two Sum (เริ่มจากศูนย์)

9. ตัวอย่างโค้ด JavaScript พร้อมวิเคราะห์ Time และ Space

ตัวอย่างหลัก: Two Sum

ตัวอย่างเสริม: ตรวจข้อมูลซ้ำ

10. กรณีที่ควรสนใจ Time มากกว่า

11. กรณีที่ควรสนใจ Space มากกว่า

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

13. ตารางเปรียบเทียบ Time vs Space แบบเข้าใจง่าย

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

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

ข้อ 2ในโจทย์ Two Sum ทำไมวิธีแฮชแมป (Hash Map) จึงเร็วกว่า Brute Forceกดเพื่อดูแนวเฉลย

ข้อ 3ถ้าระบบทำงานบนอุปกรณ์หน่วยความจำจำกัดมาก ควรระวังเรื่องใดเป็นพิเศษระหว่าง Time กับ Spaceกดเพื่อดูแนวเฉลย

ข้อ 4คำว่า trade-off ในบริบท Time vs Space หมายถึงอะไรกดเพื่อดูแนวเฉลย

Loading

Data Structures & Algorithms

1. Time Complexity คืออะไร

2. Space Complexity คืออะไร

3. ทำไมต้องวิเคราะห์ทั้งสองอย่าง

4. ความต่างระหว่างเวลาในการทำงานกับการใช้หน่วยความจำ

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

6. อธิบายแนวคิด trade-off

7. ตัวอย่างอัลกอริทึมที่ใช้เวลาน้อยแต่ใช้หน่วยความจำมาก

8. ตัวอย่างอัลกอริทึมที่ใช้หน่วยความจำน้อยแต่ใช้เวลามาก

Lab (ก่อนหัวข้อ 9): ลองทำ Two Sum แล้วดูเวลาเทียบกัน

Warm-up Lab: Two Sum (เริ่มจากศูนย์)

9. ตัวอย่างโค้ด JavaScript พร้อมวิเคราะห์ Time และ Space

ตัวอย่างหลัก: Two Sum

ตัวอย่างเสริม: ตรวจข้อมูลซ้ำ

10. กรณีที่ควรสนใจ Time มากกว่า

11. กรณีที่ควรสนใจ Space มากกว่า

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

13. ตารางเปรียบเทียบ Time vs Space แบบเข้าใจง่าย

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

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

ข้อ 2ในโจทย์ Two Sum ทำไมวิธีแฮชแมป (Hash Map) จึงเร็วกว่า Brute Forceกดเพื่อดูแนวเฉลย

ข้อ 3ถ้าระบบทำงานบนอุปกรณ์หน่วยความจำจำกัดมาก ควรระวังเรื่องใดเป็นพิเศษระหว่าง Time กับ Spaceกดเพื่อดูแนวเฉลย

ข้อ 4คำว่า trade-off ในบริบท Time vs Space หมายถึงอะไรกดเพื่อดูแนวเฉลย