Array-a01

02Learn

บทเรียน

Array-a

Big-O Notation

O(n!) — Factorial Time

เรียนรู้ O(n!) Factorial Time — operations ที่จำนวนขั้นตอนโตแบบ factorial (n × (n-1) × ... × 1) โตเร็วกว่า O(2ⁿ) ด้วยซ้ำ เกิดจากการสร้าง permutations ทั้งหมด พร้อม 6 Labs ฝึกเขียน factorial, countPermutations, swapElements, generatePermutations, permutationsOfString, และ nextPermutation

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

O(n!) หรือ **Factorial Time** หมายความว่า จำนวนขั้นตอนเท่ากับ **n! = n × (n-1) × (n-2) × ... × 1** — เป็นการเติบโตที่เร็วกว่า O(2ⁿ) ด้วยซ้ำ เมื่อ n โตขึ้นงานพุ่งกระฉูดในไม่กี่ค่า

O(n!) — n! โตเร็วแค่ไหนJS

// n! = n × (n-1) × (n-2) × ... × 1
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(3));  // 6
console.log(factorial(5));  // 120
console.log(factorial(10)); // 3,628,800
console.log(factorial(15)); // ~1.3 ล้านล้าน

ลองนึกภาพ: มีหนังสือ 3 เล่มจะเรียงบนชั้น — เรียงได้ 3! = 6 วิธี (ABC, ACB, BAC, BCA, CAB, CBA) ถ้ามี 5 เล่ม เรียงได้ 120 วิธี, 10 เล่ม เรียงได้ 3,628,800 วิธี — นี่คือ O(n!) ที่ใช้ในปัญหา permutations

ทำไม n! ถึงโตเร็วกว่า 2ⁿ

เพราะใน n! แต่ละขั้นตอนคูณด้วย n, n-1, n-2, ... ซึ่งเป็นตัวเลขที่ลดลงแต่ยังมากกว่า 2 (จนถึง n = 3) — ในขณะที่ 2ⁿ = 2 × 2 × 2 × ... (n ครั้ง) คูณด้วย 2 คงที่ทุกครั้ง

n	O(n!)	O(2ⁿ)	O(n²)
3	6	8	9
5	120	32	25
7	5,040	128	49
10	3,628,800	1,024	100
15	~1.3×10¹²	32,768	225

สังเกต: ที่ n=7, n! แซง 2ⁿ ไปแล้ว (5,040 > 128) — และยิ่ง n ใหญ่ขึ้น n! จะยิ่งทิ้งห่าง 2ⁿ มากขึ้นเรื่อยๆ เพราะ n! คูณด้วยตัวเลขที่ใหญ่ขึ้นทุกรอบ

ตัวอย่าง O(n!): สร้าง permutations ทั้งหมด

การสร้าง **permutations** ทั้งหมดของ array — จำนวน permutations = n! — ต้องใช้เวลา O(n! × n) เพราะมี n! แบบ และแต่ละแบบใช้เวลา O(n) ในการสร้าง/คัดลอก

Generate permutations — O(n!)JS

function generatePermutations(arr) {
  const result = [];

  function permute(current, remaining) {
    if (remaining.length === 0) {
      result.push(current.slice());
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      const rest = remaining.slice(0, i).concat(remaining.slice(i + 1));
      permute(current, rest);
      current.pop();
    }
  }

  permute([], arr);
  return result;
}

console.log(generatePermutations(["a", "b", "c"]).length); // 6 = 3!
console.log(generatePermutations([1, 2, 3, 4]).length);    // 24 = 4!

มี n! permutations — ถ้า n = 10, มี 3,628,800 permutations — ใหญ่พอที่จะทำให้เบราว์เซอร์ค้าง นี่คือเหตุผลที่เราไม่ใช้ O(n!) กับข้อมูลขนาดใหญ่

ตัวอย่าง O(n!): Traveling Salesman brute force

**Traveling Salesman Problem (TSP)** — หาเส้นทางที่สั้นที่สุดที่ผ่านทุกเมืองแล้วกลับจุดเริ่ม — ถ้าใช้ brute force ต้องลองทุก permutation ของลำดับเมือง = (n-1)! เส้นทาง

TSP brute force concept — O(n!)JS

// TSP brute force concept
function tspBruteForce(points) {
  // จำนวนเส้นทางทั้งหมด = (n-1)! / 2 (นับไป-กลับเป็นเส้นทางเดียว)
  // n = 5 → 12 เส้นทาง
  // n = 10 → 181,440 เส้นทาง
  // n = 15 → ~43,000,000,000 เส้นทาง — เป็นไปไม่ได้ในทางปฏิบัติ!

  const n = points.length;
  const permutations = factorial(n - 1); // approx
  return permutations;
}

// n = 15 เมือง → ต้องลอง 87,178,291,200 เส้นทาง
// แม้แต่คอมพิวเตอร์ที่คำนวณ 1,000,000 เส้นทาง/วินาที
// ก็ต้องใช้เวลา ~24 ชั่วโมง

TSP brute force แสดงให้เห็นว่า O(n!) ไม่เหมาะกับ n > 10-12 — ในทางปฏิบัติเราใช้ heuristic หรือ dynamic programming แทน

ตัวอย่าง O(n!): จำนวน derangements

**Derangement** คือ permutation ที่ไม่มีสมาชิกตัวใดอยู่ตำแหน่งเดิม — จำนวน derangements = !n (subfactorial) ≈ n!/e — ยังเป็น O(n!) อยู่

Derangement count — O(n!)JS

// !n = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)
// formula: !n = (n-1) × (!(n-1) + !(n-2))
function countDerangements(n) {
  if (n === 0) return 1;
  if (n === 1) return 0;
  return (n - 1) * (countDerangements(n - 1) + countDerangements(n - 2));
}

console.log(countDerangements(3)); // 2 (BCA, CAB)
console.log(countDerangements(4)); // 9

ถึงฟังก์ชันนี้ใช้ recursion แต่จำนวน derangements เองเป็น O(n!) — และการหา derangements ทั้งหมดก็จะเป็น O(n!) เช่นกัน

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

เข้าใจผิดบ่อยที่สุดคือ คิดว่าฟังก์ชันที่ใช้ factorial เป็น O(n!) — การคำนวณ factorial(n) ใช้เวลา O(n) แต่ปัญหาที่สร้าง permutations ทั้งหมดเป็น O(n!)

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

// ❌ คำนวณ n! — O(n) ไม่ใช่ O(n!)
function factorial(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

// ❌ ทำ O(1) with Set — O(n) ไม่ใช่ O(n!)
function hasDuplicate(arr) {
  return arr.length !== new Set(arr).size;
}

// ❌ Fibonacci — O(2ⁿ) ไม่ใช่ O(n!)
// (n! โตเร็วกว่า 2ⁿ มาก)

// ❌ Nested loop — O(n²) ไม่ใช่ O(n!)
function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

กฎง่ายๆ: **O(n!) ต้อง "สร้างทุก permutation" หรือ "ลองทุกลำดับที่เป็นไปได้" — ไม่ใช่แค่คำนวณ factorial เฉยๆ**

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

O(n!) — Factorial Time

Operations ที่จำนวนขั้นตอนโตแบบ n × (n-1) × ... × 1 — โตเร็วกว่า 2ⁿ

O(n!)

สร้าง permutations ทั้งหมด

n! permutations — ต้องสร้างทุกแบบ = O(n! × n)

O(n!)

Traveling Salesman (brute force)

ลองทุกเส้นทาง = (n-1)! / 2 เส้นทาง — เป็น O(n!)

O(n!)

นับจำนวน permutations (n!)

คำนวณ n! ใช้เวลา O(n) — แต่จำนวนผลลัพธ์ = O(n!)

O(n!)

สร้าง derangements ทั้งหมด

จำนวน derangements ≈ n!/e — ยังเป็น O(n!)

NOT O(n!)

คำนวณ factorial(n)

O(n) เท่านั้น — ไม่ใช่ O(n!) ในแง่ runtime

NOT O(n!)

Nested loop / fibonacci

O(n²) หรือ O(2ⁿ) — ไม่ใช่ O(n!)

Lab 1: คำนวณค่า n!

Lab 2: นับจำนวน permutations

Lab 3: สลับค่าสองตำแหน่ง (helper)

Lab 4: สร้าง permutations ทั้งหมด

Lab 5: สร้าง permutations ของ string

Lab 6: หา next permutation (lexicographic order)

สรุป O(n!) Operations

Operation	ตัวอย่าง	ความเร็ว
คำนวณ n! (runtime)	factorial(n)	O(n)
นับจำนวน permutations	countPermutations(arr)	O(n)
สลับค่าสองตำแหน่ง	swapElements(arr, i, j)	O(1)
สร้าง permutations ทั้งหมด	generatePermutations(arr)	O(n!)
Permutations ของ string	permutationsOfString(str)	O(n!)
Next permutation	nextPermutation(arr)	O(n)
Loop เดียว	for (const x of arr)	O(n) ❌
Nested loop	for + for	O(n²) ❌

Array-a01

02Learn

Array-a Learn

กำลังโหลดบทเรียน...

Big-O Notation

O(n!) — Factorial Time

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

O(n!) — n! โตเร็วแค่ไหนJS

// n! = n × (n-1) × (n-2) × ... × 1
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(3));  // 6
console.log(factorial(5));  // 120
console.log(factorial(10)); // 3,628,800
console.log(factorial(15)); // ~1.3 ล้านล้าน

ทำไม n! ถึงโตเร็วกว่า 2ⁿ

n	O(n!)	O(2ⁿ)	O(n²)
3	6	8	9
5	120	32	25
7	5,040	128	49
10	3,628,800	1,024	100
15	~1.3×10¹²	32,768	225

ตัวอย่าง O(n!): สร้าง permutations ทั้งหมด

Generate permutations — O(n!)JS

function generatePermutations(arr) {
  const result = [];

  function permute(current, remaining) {
    if (remaining.length === 0) {
      result.push(current.slice());
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      const rest = remaining.slice(0, i).concat(remaining.slice(i + 1));
      permute(current, rest);
      current.pop();
    }
  }

  permute([], arr);
  return result;
}

console.log(generatePermutations(["a", "b", "c"]).length); // 6 = 3!
console.log(generatePermutations([1, 2, 3, 4]).length);    // 24 = 4!

ตัวอย่าง O(n!): Traveling Salesman brute force

TSP brute force concept — O(n!)JS

// TSP brute force concept
function tspBruteForce(points) {
  // จำนวนเส้นทางทั้งหมด = (n-1)! / 2 (นับไป-กลับเป็นเส้นทางเดียว)
  // n = 5 → 12 เส้นทาง
  // n = 10 → 181,440 เส้นทาง
  // n = 15 → ~43,000,000,000 เส้นทาง — เป็นไปไม่ได้ในทางปฏิบัติ!

  const n = points.length;
  const permutations = factorial(n - 1); // approx
  return permutations;
}

// n = 15 เมือง → ต้องลอง 87,178,291,200 เส้นทาง
// แม้แต่คอมพิวเตอร์ที่คำนวณ 1,000,000 เส้นทาง/วินาที
// ก็ต้องใช้เวลา ~24 ชั่วโมง

ตัวอย่าง O(n!): จำนวน derangements

Derangement count — O(n!)JS

// !n = n! × (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)
// formula: !n = (n-1) × (!(n-1) + !(n-2))
function countDerangements(n) {
  if (n === 0) return 1;
  if (n === 1) return 0;
  return (n - 1) * (countDerangements(n - 1) + countDerangements(n - 2));
}

console.log(countDerangements(3)); // 2 (BCA, CAB)
console.log(countDerangements(4)); // 9

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

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

// ❌ คำนวณ n! — O(n) ไม่ใช่ O(n!)
function factorial(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

// ❌ ทำ O(1) with Set — O(n) ไม่ใช่ O(n!)
function hasDuplicate(arr) {
  return arr.length !== new Set(arr).size;
}

// ❌ Fibonacci — O(2ⁿ) ไม่ใช่ O(n!)
// (n! โตเร็วกว่า 2ⁿ มาก)

// ❌ Nested loop — O(n²) ไม่ใช่ O(n!)
function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

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

O(n!) — Factorial Time

Operations ที่จำนวนขั้นตอนโตแบบ n × (n-1) × ... × 1 — โตเร็วกว่า 2ⁿ

O(n!)

สร้าง permutations ทั้งหมด

n! permutations — ต้องสร้างทุกแบบ = O(n! × n)

O(n!)

Traveling Salesman (brute force)

ลองทุกเส้นทาง = (n-1)! / 2 เส้นทาง — เป็น O(n!)

O(n!)

นับจำนวน permutations (n!)

คำนวณ n! ใช้เวลา O(n) — แต่จำนวนผลลัพธ์ = O(n!)

O(n!)

สร้าง derangements ทั้งหมด

จำนวน derangements ≈ n!/e — ยังเป็น O(n!)

NOT O(n!)

คำนวณ factorial(n)

O(n) เท่านั้น — ไม่ใช่ O(n!) ในแง่ runtime

NOT O(n!)

Nested loop / fibonacci

O(n²) หรือ O(2ⁿ) — ไม่ใช่ O(n!)

Lab 1: คำนวณค่า n!

Lab 2: นับจำนวน permutations

Lab 3: สลับค่าสองตำแหน่ง (helper)

Lab 4: สร้าง permutations ทั้งหมด

Lab 5: สร้าง permutations ของ string

Lab 6: หา next permutation (lexicographic order)

สรุป O(n!) Operations

Operation	ตัวอย่าง	ความเร็ว
คำนวณ n! (runtime)	factorial(n)	O(n)
นับจำนวน permutations	countPermutations(arr)	O(n)
สลับค่าสองตำแหน่ง	swapElements(arr, i, j)	O(1)
สร้าง permutations ทั้งหมด	generatePermutations(arr)	O(n!)
Permutations ของ string	permutationsOfString(str)	O(n!)
Next permutation	nextPermutation(arr)	O(n)
Loop เดียว	for (const x of arr)	O(n) ❌
Nested loop	for + for	O(n²) ❌

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

ทำไม n! ถึงโตเร็วกว่า 2ⁿ

ตัวอย่าง O(n!): สร้าง permutations ทั้งหมด

ตัวอย่าง O(n!): Traveling Salesman brute force

ตัวอย่าง O(n!): จำนวน derangements

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

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

O(n!) — Factorial Time

สร้าง permutations ทั้งหมด

Traveling Salesman (brute force)

นับจำนวน permutations (n!)

สร้าง derangements ทั้งหมด

คำนวณ factorial(n)

Nested loop / fibonacci

Lab 1: คำนวณค่า n!

Lab 2: นับจำนวน permutations

Lab 3: สลับค่าสองตำแหน่ง (helper)

Lab 4: สร้าง permutations ทั้งหมด

Lab 5: สร้าง permutations ของ string

Lab 6: หา next permutation (lexicographic order)

สรุป O(n!) Operations

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

O(n!) — Factorial Time

array ความยาว 4 มีกี่ permutations?

O(n!) เทียบกับ O(2ⁿ) ต่างกันยังไง?

การคำนวณ n! ใช้ runtime เท่าไหร่?

กำลังโหลดบทเรียน...

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

ทำไม n! ถึงโตเร็วกว่า 2ⁿ

ตัวอย่าง O(n!): สร้าง permutations ทั้งหมด

ตัวอย่าง O(n!): Traveling Salesman brute force

ตัวอย่าง O(n!): จำนวน derangements

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

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

O(n!) — Factorial Time

สร้าง permutations ทั้งหมด

Traveling Salesman (brute force)

นับจำนวน permutations (n!)

สร้าง derangements ทั้งหมด

คำนวณ factorial(n)

Nested loop / fibonacci

Lab 1: คำนวณค่า n!

Lab 2: นับจำนวน permutations

Lab 3: สลับค่าสองตำแหน่ง (helper)

Lab 4: สร้าง permutations ทั้งหมด

Lab 5: สร้าง permutations ของ string

Lab 6: หา next permutation (lexicographic order)

สรุป O(n!) Operations

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

O(n!) — Factorial Time

array ความยาว 4 มีกี่ permutations?

O(n!) เทียบกับ O(2ⁿ) ต่างกันยังไง?

การคำนวณ n! ใช้ runtime เท่าไหร่?

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

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