Array-a01

02Learn

บทเรียน

Array-a

Big-O Notation

O(n²) — Quadratic Time

เรียนรู้ O(n²) Quadratic Time — operations ที่จำนวนขั้นตอนโตแบบกำลังสองของขนาดข้อมูล เกิดจาก nested loops และ sorting algorithm พื้นฐาน พร้อม 6 Labs ฝึกเขียน countPairs, findDuplicates, multiplicationTable, bubblePass, findClosestPair, และ selectionSort

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

O(n²) หรือ **Quadratic Time** หมายความว่า จำนวนขั้นตอนเติบโตแบบ **กำลังสอง**ของขนาดข้อมูล n — ถ้าข้อมูลโต 10 เท่า งานจะโตประมาณ 100 เท่า

O(n²) — nested loop สองชั้นJS

// เทียบคู่ทุกคนในห้อง — จำนวนการจับคู่ ≈ n²/2
const names = ["Anna", "Bob", "Charlie", "Diana"];
for (let i = 0; i < names.length; i++) {
  for (let j = i + 1; j < names.length; j++) {
    console.log(names[i], "เจอ", names[j]);
  }
}
// 4 คน → 6 คู่, 100 คน → 4,950 คู่

ลองนึกภาพ: มีคน n คนในงานเลี้ยง และทุกคนต้องจับมือกับทุกคน — คนแรกจับมือ n-1 คน, คนที่สองจับมือ n-2 คน, ... รวมเป็น (n×(n-1))/2 ≈ n²/2 ครั้ง — นี่คือ O(n²) ยิ่งคนมาก ยิ่งทวีคูณเร็วมาก

ทำไม O(n²) ถึงเติบโตเร็ว

เพราะแต่ละรอบของ loop นอก (n รอบ) มี loop ในที่วิ่งตามสัดส่วน n อีกที — งานรวมจึงเป็น n × n = n²

n (ขนาดข้อมูล)	O(n) ขั้นตอน	O(n²) ขั้นตอน	O(n log n) ขั้นตอน
10	10	100	~33
100	100	10,000	~664
1,000	1,000	1,000,000	~9,966
10,000	10,000	100,000,000	~132,877

สังเกต: เมื่อ n เพิ่ม 10 เท่า (จาก 100 เป็น 1,000) O(n²) เพิ่ม 100 เท่า (10,000 → 1,000,000) — ต่างจาก O(n) ที่เพิ่มแค่ 10 เท่า

ตัวอย่าง O(n²): nested loop เทียบคู่

รูปแบบที่พบบ่อยที่สุดของ O(n²) คือ **nested loop** — loop นอกวิ่ง n รอบ และทุกรอบของ loop นอกมี loop ในวิ่งตามสัดส่วน n

Nested loop — O(n²)JS

// พิมพ์ทุกคู่ของข้อมูล
function printAllPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

printAllPairs(["A", "B", "C"]);
// A A, A B, A C, B A, B B, B C, C A, C B, C C
// 3 ตัว → 9 คู่ = n²

กฎง่ายๆ: **loop นอก n รอบ × loop ใน n รอบ = n² รอบ → O(n²)**

ตัวอย่าง O(n²): ตรวจหาค่าซ้ำด้วย nested loop

การตรวจว่ามีค่าซ้ำใน array หรือไม่ด้วย nested loop — loop นอกไล่ทุกตัว, loop ในเทียบกับตัวที่อยู่ถัดไป — เป็น O(n²)

Find duplicate — O(n²)JS

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

console.log(hasDuplicate([3, 7, 2, 9, 3])); // true
console.log(hasDuplicate([1, 2, 3, 4]));    // false

เทียบกับวิธีที่ใช้ Set: ใช้ Set = O(n) เร็วกว่า — แต่วิธี nested loop เป็น O(n²) ที่เข้าใจง่ายกว่าเมื่อเริ่มต้น

ตัวอย่าง O(n²): Bubble Sort / Selection Sort / Insertion Sort

Algorithm สำหรับเรียงลำดับขั้นพื้นฐาน เช่น **Bubble Sort**, **Selection Sort**, และ **Insertion Sort** ล้วนทำงานใน O(n²) — เพราะใช้ nested loops เปรียบเทียบและสลับข้อมูล

Bubble sort concept — O(n²)JS

// Bubble sort: ดันค่ามากสุดไปด้านหลังทีละรอบ
function bubbleSort(arr) {
  const result = arr.slice(); // อย่าแก้ต้นฉบับ
  for (let i = 0; i < result.length; i++) {
    for (let j = 0; j < result.length - i - 1; j++) {
      if (result[j] > result[j + 1]) {
        // swap
        const temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }
  return result;
}

console.log(bubbleSort([5, 2, 8, 1, 4]));
// [1, 2, 4, 5, 8]

เราจะเจาะลึก Bubble Sort, Selection Sort, Insertion Sort เพิ่มเติมใน phase Basic Sorting — ตอนนี้ให้เข้าใจว่า nested loops เป็นหัวใจของ O(n²)

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

เข้าใจผิดบ่อยที่สุดคือ คิดว่า loop สองอันแยกกันเป็น O(n²) ความจริงคือ **ต้องซ้อนกัน** (nested) ถึงจะเป็น O(n²) — ถ้าอยู่แยกกันคนละบรรทัด ไม่ได้ซ้อนกัน จะเป็น O(n) + O(n) = O(2n) = O(n)

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

const arr = [10, 20, 30, 40, 50];

// ❌ loop เดียว — O(n) ไม่ใช่ O(n²)
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

// ❌ สอง loop แยกกัน — O(n) + O(n) = O(n) ไม่ใช่ O(n²)
for (const x of arr) { console.log(x); }
for (const x of arr) { console.log(x * 2); }

// ❌ array access by index — O(1) ไม่ใช่ O(n²)
console.log(arr[2]);

// ❌ binary search — O(log n) ไม่ใช่ O(n²)
// (ตัดครึ่งทุกรอบ)

กฎง่ายๆ: **O(n²) = loop นอก × loop ใน — สอง loop อยู่ในกัน ไม่ใช่แยกกัน**

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

O(n²) — Quadratic Time

Operations ที่จำนวนขั้นตอนโตแบบกำลังสองของ n

O(n²)

Nested loop สองชั้น (เต็ม n × n)

loop นอกวิ่ง n รอบ, loop ในวิ่ง n รอบ — งานรวม = n²

O(n²)

การเทียบคู่ (pair comparison)

เทียบทุกคู่ = n(n-1)/2 ≈ n²/2 — ยังเป็น O(n²) (ตัดค่าคงที่)

O(n²)

Bubble Sort / Selection Sort / Insertion Sort

Sorting algorithm พื้นฐาน — nested loop = O(n²)

O(n²)

ตารางคูณ / matrix n×n

สร้างตาราง n×n = O(n²) เพราะต้องเติมทุกช่อง n² ช่อง

NOT O(n²)

Single loop วิ่ง n รอบ

loop เดียว = O(n) ไม่ใช่ O(n²)

NOT O(n²)

สอง loop แยกกัน (sequential loops)

O(n) + O(n) = O(2n) = O(n) — ไม่ใช่ O(n²)

Lab 1: นับจำนวนคู่ทั้งหมด

Lab 2: ตรวจหาค่าซ้ำด้วย nested loop

Lab 3: สร้างตารางคูณ n×n

Lab 4: Bubble sort หนึ่งรอบ

Lab 5: หาคู่ที่ใกล้กันที่สุด

Lab 6: Selection sort

สรุป O(n²) Operations

Operation	ตัวอย่าง	ความเร็ว
นับจำนวนคู่ทั้งหมด	countPairs(n)	O(n²)
ตรวจหาค่าซ้ำ (nested loop)	findDuplicates(arr)	O(n²)
สร้างตาราง n×n	multiplicationTable(n)	O(n²)
Bubble sort หนึ่งรอบ	bubblePass(arr)	O(n)
หาคู่ที่ใกล้กันที่สุด	findClosestPair(arr)	O(n²)
Selection sort	selectionSort(arr)	O(n²)
Loop เดียว	for (const x of arr)	O(n) ❌
Array access by index	arr[3]	O(1) ❌

Array-a01

02Learn

Array-a Learn

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

Big-O Notation

O(n²) — Quadratic Time

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

O(n²) — nested loop สองชั้นJS

// เทียบคู่ทุกคนในห้อง — จำนวนการจับคู่ ≈ n²/2
const names = ["Anna", "Bob", "Charlie", "Diana"];
for (let i = 0; i < names.length; i++) {
  for (let j = i + 1; j < names.length; j++) {
    console.log(names[i], "เจอ", names[j]);
  }
}
// 4 คน → 6 คู่, 100 คน → 4,950 คู่

ทำไม O(n²) ถึงเติบโตเร็ว

n (ขนาดข้อมูล)	O(n) ขั้นตอน	O(n²) ขั้นตอน	O(n log n) ขั้นตอน
10	10	100	~33
100	100	10,000	~664
1,000	1,000	1,000,000	~9,966
10,000	10,000	100,000,000	~132,877

ตัวอย่าง O(n²): nested loop เทียบคู่

Nested loop — O(n²)JS

// พิมพ์ทุกคู่ของข้อมูล
function printAllPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

printAllPairs(["A", "B", "C"]);
// A A, A B, A C, B A, B B, B C, C A, C B, C C
// 3 ตัว → 9 คู่ = n²

กฎง่ายๆ: **loop นอก n รอบ × loop ใน n รอบ = n² รอบ → O(n²)**

ตัวอย่าง O(n²): ตรวจหาค่าซ้ำด้วย nested loop

Find duplicate — O(n²)JS

function hasDuplicate(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

console.log(hasDuplicate([3, 7, 2, 9, 3])); // true
console.log(hasDuplicate([1, 2, 3, 4]));    // false

ตัวอย่าง O(n²): Bubble Sort / Selection Sort / Insertion Sort

Bubble sort concept — O(n²)JS

// Bubble sort: ดันค่ามากสุดไปด้านหลังทีละรอบ
function bubbleSort(arr) {
  const result = arr.slice(); // อย่าแก้ต้นฉบับ
  for (let i = 0; i < result.length; i++) {
    for (let j = 0; j < result.length - i - 1; j++) {
      if (result[j] > result[j + 1]) {
        // swap
        const temp = result[j];
        result[j] = result[j + 1];
        result[j + 1] = temp;
      }
    }
  }
  return result;
}

console.log(bubbleSort([5, 2, 8, 1, 4]));
// [1, 2, 4, 5, 8]

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

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

const arr = [10, 20, 30, 40, 50];

// ❌ loop เดียว — O(n) ไม่ใช่ O(n²)
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}

// ❌ สอง loop แยกกัน — O(n) + O(n) = O(n) ไม่ใช่ O(n²)
for (const x of arr) { console.log(x); }
for (const x of arr) { console.log(x * 2); }

// ❌ array access by index — O(1) ไม่ใช่ O(n²)
console.log(arr[2]);

// ❌ binary search — O(log n) ไม่ใช่ O(n²)
// (ตัดครึ่งทุกรอบ)

กฎง่ายๆ: **O(n²) = loop นอก × loop ใน — สอง loop อยู่ในกัน ไม่ใช่แยกกัน**

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

O(n²) — Quadratic Time

Operations ที่จำนวนขั้นตอนโตแบบกำลังสองของ n

O(n²)

Nested loop สองชั้น (เต็ม n × n)

loop นอกวิ่ง n รอบ, loop ในวิ่ง n รอบ — งานรวม = n²

O(n²)

การเทียบคู่ (pair comparison)

เทียบทุกคู่ = n(n-1)/2 ≈ n²/2 — ยังเป็น O(n²) (ตัดค่าคงที่)

O(n²)

Bubble Sort / Selection Sort / Insertion Sort

Sorting algorithm พื้นฐาน — nested loop = O(n²)

O(n²)

ตารางคูณ / matrix n×n

สร้างตาราง n×n = O(n²) เพราะต้องเติมทุกช่อง n² ช่อง

NOT O(n²)

Single loop วิ่ง n รอบ

loop เดียว = O(n) ไม่ใช่ O(n²)

NOT O(n²)

สอง loop แยกกัน (sequential loops)

O(n) + O(n) = O(2n) = O(n) — ไม่ใช่ O(n²)

Lab 1: นับจำนวนคู่ทั้งหมด

Lab 2: ตรวจหาค่าซ้ำด้วย nested loop

Lab 3: สร้างตารางคูณ n×n

Lab 4: Bubble sort หนึ่งรอบ

Lab 5: หาคู่ที่ใกล้กันที่สุด

Lab 6: Selection sort

สรุป O(n²) Operations

Operation	ตัวอย่าง	ความเร็ว
นับจำนวนคู่ทั้งหมด	countPairs(n)	O(n²)
ตรวจหาค่าซ้ำ (nested loop)	findDuplicates(arr)	O(n²)
สร้างตาราง n×n	multiplicationTable(n)	O(n²)
Bubble sort หนึ่งรอบ	bubblePass(arr)	O(n)
หาคู่ที่ใกล้กันที่สุด	findClosestPair(arr)	O(n²)
Selection sort	selectionSort(arr)	O(n²)
Loop เดียว	for (const x of arr)	O(n) ❌
Array access by index	arr[3]	O(1) ❌

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

ทำไม O(n²) ถึงเติบโตเร็ว

ตัวอย่าง O(n²): nested loop เทียบคู่

ตัวอย่าง O(n²): ตรวจหาค่าซ้ำด้วย nested loop

ตัวอย่าง O(n²): Bubble Sort / Selection Sort / Insertion Sort

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

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

O(n²) — Quadratic Time

Nested loop สองชั้น (เต็ม n × n)

การเทียบคู่ (pair comparison)

Bubble Sort / Selection Sort / Insertion Sort

ตารางคูณ / matrix n×n

Single loop วิ่ง n รอบ

สอง loop แยกกัน (sequential loops)

Lab 1: นับจำนวนคู่ทั้งหมด

Lab 2: ตรวจหาค่าซ้ำด้วย nested loop

Lab 3: สร้างตารางคูณ n×n

Lab 4: Bubble sort หนึ่งรอบ

Lab 5: หาคู่ที่ใกล้กันที่สุด

Lab 6: Selection sort

สรุป O(n²) Operations

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

O(n²) — Quadratic Time

operation ไหนที่เป็น O(n²)?

ทำไม nested loop ถึงเป็น O(n²)?

ถ้า n เพิ่มจาก 10 เป็น 100 เวลาของ O(n²) เพิ่มกี่เท่า?

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

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

ทำไม O(n²) ถึงเติบโตเร็ว

ตัวอย่าง O(n²): nested loop เทียบคู่

ตัวอย่าง O(n²): ตรวจหาค่าซ้ำด้วย nested loop

ตัวอย่าง O(n²): Bubble Sort / Selection Sort / Insertion Sort

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

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

O(n²) — Quadratic Time

Nested loop สองชั้น (เต็ม n × n)

การเทียบคู่ (pair comparison)

Bubble Sort / Selection Sort / Insertion Sort

ตารางคูณ / matrix n×n

Single loop วิ่ง n รอบ

สอง loop แยกกัน (sequential loops)

Lab 1: นับจำนวนคู่ทั้งหมด

Lab 2: ตรวจหาค่าซ้ำด้วย nested loop

Lab 3: สร้างตารางคูณ n×n

Lab 4: Bubble sort หนึ่งรอบ

Lab 5: หาคู่ที่ใกล้กันที่สุด

Lab 6: Selection sort

สรุป O(n²) Operations

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

O(n²) — Quadratic Time

operation ไหนที่เป็น O(n²)?

ทำไม nested loop ถึงเป็น O(n²)?

ถ้า n เพิ่มจาก 10 เป็น 100 เวลาของ O(n²) เพิ่มกี่เท่า?

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

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