Array-a01

02Learn

บทเรียน

Array-a

Big-O Notation

O(n) — Linear Time

เรียนรู้ O(n) Linear Time — operations ที่จำนวนขั้นตอนเติบโตตามสัดส่วนกับขนาดข้อมูล พร้อม 6 Labs ฝึกเขียน count, findMax, sum, linearSearch, filter, และ countIf

O(n) คืออะไร

O(n) หรือ **Linear Time** หมายความว่า จำนวนขั้นตอนเติบโต **ตามสัดส่วน**กับขนาดข้อมูล n — ถ้าข้อมูลมี 10 เท่า ก็ใช้เวลาประมาณ 10 เท่า

O(n) — ไล่ทุกตัวJS

// ต้องพิมพ์ทุกชื่อ — จำนวนรอบ = จำนวนสมาชิก
const names = ["Anna", "Bob", "Charlie", "Diana"];

for (let i = 0; i < names.length; i++) {
  console.log(names[i]);
}
// 4 ตัว → 4 รอบ, 100 ตัว → 100 รอบ

ลองนึกภาพ: คุณมีกระปุกเหรียญและต้องการนับว่ามีกี่เหรียญ ถ้ามี 10 เหรียญก็ใช้เวลาหนึ่ง ถ้า 100 เหรียญก็ใช้เวลาประมาณ 10 เท่า — ต้องจับทุกเหรียญ ไม่มีทางข้าม นี่คือ O(n)

ทำไม O(n) ถึงเติบโตเป็นเส้นตรง

เพราะทุกขั้นตอนดูข้อมูล **1 ชิ้น** และทำซ้ำ n ครั้ง — ไม่มีการข้าม ไม่มีการตัดทิ้ง จำนวนรอบจึงเท่ากับ n ทีเดียว

n (ขนาดข้อมูล)	จำนวนขั้นตอน	เทียบกับ O(log n)
10	10	~3
100	100	~7
1,000	1,000	~10
10,000	10,000	~13
100,000	100,000	~16

สังเกต: เมื่อ n เพิ่ม 10 เท่า (จาก 1,000 เป็น 10,000) เวลาก็เพิ่ม 10 เท่า — ต่างจาก O(log n) ที่เพิ่มแค่ 3 รอบ

ตัวอย่าง O(n): ไล่อ่านทุกตัวใน array

รูปแบบที่พบบ่อยที่สุดของ O(n) คือ **single loop** ที่วิ่งผ่านทุก element ของ array ไม่ว่าจะใช้ `for`, `for...of`, หรือ `forEach` — ทั้งหมดเป็น O(n) เมื่อวิ่งจากต้นจนจบ

Single loop — O(n) ทุกรูปแบบJS

const prices = [100, 250, 80, 320, 150];

// แบบที่ 1: for loop
for (let i = 0; i < prices.length; i++) {
  console.log(prices[i]);
}

// แบบที่ 2: for...of
for (const price of prices) {
  console.log(price);
}

// แบบที่ 3: forEach
prices.forEach((price) => {
  console.log(price);
});

กฎง่ายๆ: **ถ้ามี loop 1 ชั้นที่วิ่งจากต้นจนจบ array และไม่มี loop ซ้อน — นั่นคือ O(n)**

ตัวอย่าง O(n): หาค่าสูงสุด/ต่ำสุด

เพื่อหาค่ามากที่สุดใน array ที่ **ไม่ได้เรียงลำดับ** เราต้องตรวจทุกตัว — เพราะถ้าข้ามแม้แต่ตัวเดียว อาจพลาดค่ามากที่สุด

Find max — O(n)JS

function findMax(arr) {
  let max = arr[0];          // เริ่มจากตัวแรก
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];          // เจอตัวที่มากกว่า → เก็บไว้
    }
  }
  return max;
}

console.log(findMax([3, 7, 2, 9, 1]));   // 9
console.log(findMax([50, 20, 80, 10]));  // 80

สังเกต: ถ้า array **เรียงแล้ว** การหา max/min เป็น O(1) (ดูตัวแรกหรือตัวสุดท้าย) — แต่ถ้าไม่เรียง ต้องเป็น O(n) เสมอ

ตัวอย่าง O(n): ค้นหาแบบ linear search

การหาค่าใน array ที่ไม่เรียงลำดับ ต้องไล่ดูทีละตัวตั้งแต่ต้นจนเจอ (หรือจนหมด) — เรียกว่า **linear search**

Linear search — O(n)JS

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

const nums = [15, 42, 8, 23, 4];

console.log(linearSearch(nums, 23));  // 3
console.log(linearSearch(nums, 99));  // -1

เปรียบเทียบกับ O(log n): binary search เร็วกว่า (ตัดครึ่งทุกรอบ) แต่ **ต้องการข้อมูลที่เรียงแล้ว** — linear search ใช้ได้กับข้อมูลทุกแบบแต่ช้ากว่า

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

เข้าใจผิดบ่อยที่สุดคือ คิดว่า loop ทุกแบบเป็น O(n) ความจริงคือ **ถ้า loop ซ้อนกัน หรือไม่ได้ไล่ทุกตัว มันไม่ใช่ O(n)**

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

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

// ❌ อ่านที่ index ที่รู้ — O(1)
console.log(arr[0]);

// ❌ ซ้อน loop 2 ชั้น — O(n²)
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    console.log(arr[i], arr[j]);
  }
}

// ❌ ตัดครึ่งทุกรอบ — O(log n)
let n = arr.length;
while (n > 1) {
  n = Math.floor(n / 2);
}

กฎง่ายๆ: **loop 1 ชั้นที่วิ่ง n รอบ = O(n)**, **ซ้อน 2 ชั้น = O(n²)**, **ไม่มี loop = O(1)**, **ตัดครึ่งทุกรอบ = O(log n)**

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

O(n) — Linear Time

Operations ที่จำนวนขั้นตอนเติบโตตามสัดส่วนกับขนาดข้อมูล

O(n)

Single loop ผ่านทุก element

for, for...of, forEach ที่วิ่งจากต้นจนจบ array — จำนวนรอบ = n

O(n)

Linear search (indexOf, find, includes)

ไล่ดูทีละตัวจนเจอ — worst case ต้องดูทุกตัว

O(n)

หา max/min ใน unsorted array

ต้องตรวจทุกตัว เพราะถ้าข้ามอาจพลาดค่ามาก/น้อยสุด

O(n)

Sum / count / filter / map / reduce

ต้องเข้าถึงทุก element เพื่อคำนวณหรือสร้างผลลัพธ์

NOT O(n)

Array access by index / Object lookup by key

กระโดดไปยังตำแหน่งที่รู้ได้ทันที — เป็น O(1) ไม่ใช่ O(n)

NOT O(n)

Nested loops / ซ้อน 2 ชั้น

ทุกรอบของ loop นอก มี loop ในวิ่ง n รอบ — เป็น O(n²) ไม่ใช่ O(n)

Lab 1: นับจำนวนค่าที่ตรงกัน

Lab 2: หาค่ามากที่สุดใน array

Lab 3: ผลรวมของทุกตัวใน array

Lab 4: ค้นหาตำแหน่งของค่าใน array

Lab 5: กรองเฉพาะค่าที่ผ่านเงื่อนไข

Lab 6: นับจำนวนที่ผ่านเงื่อนไข

สรุป O(n) Operations

Operation	ตัวอย่าง	ความเร็ว
ไล่ทุกตัวใน array	for (const x of arr)	O(n)
indexOf / find / includes	arr.indexOf(5)	O(n)
หา max/min (unsorted)	findMax(arr)	O(n)
ผลรวม / นับ	sumAll(arr)	O(n)
filter / map / reduce	arr.filter(fn)	O(n)
Linear search	linearSearch(arr, x)	O(n)
อ่าน array ด้วย index	arr[0]	O(1) ❌
ซ้อน loop 2 ชั้น	for + for	O(n²) ❌

Array-a01

02Learn

Array-a Learn

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

Big-O Notation

O(n) — Linear Time

O(n) คืออะไร

O(n) — ไล่ทุกตัวJS

// ต้องพิมพ์ทุกชื่อ — จำนวนรอบ = จำนวนสมาชิก
const names = ["Anna", "Bob", "Charlie", "Diana"];

for (let i = 0; i < names.length; i++) {
  console.log(names[i]);
}
// 4 ตัว → 4 รอบ, 100 ตัว → 100 รอบ

ทำไม O(n) ถึงเติบโตเป็นเส้นตรง

n (ขนาดข้อมูล)	จำนวนขั้นตอน	เทียบกับ O(log n)
10	10	~3
100	100	~7
1,000	1,000	~10
10,000	10,000	~13
100,000	100,000	~16

ตัวอย่าง O(n): ไล่อ่านทุกตัวใน array

Single loop — O(n) ทุกรูปแบบJS

const prices = [100, 250, 80, 320, 150];

// แบบที่ 1: for loop
for (let i = 0; i < prices.length; i++) {
  console.log(prices[i]);
}

// แบบที่ 2: for...of
for (const price of prices) {
  console.log(price);
}

// แบบที่ 3: forEach
prices.forEach((price) => {
  console.log(price);
});

กฎง่ายๆ: **ถ้ามี loop 1 ชั้นที่วิ่งจากต้นจนจบ array และไม่มี loop ซ้อน — นั่นคือ O(n)**

ตัวอย่าง O(n): หาค่าสูงสุด/ต่ำสุด

Find max — O(n)JS

function findMax(arr) {
  let max = arr[0];          // เริ่มจากตัวแรก
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];          // เจอตัวที่มากกว่า → เก็บไว้
    }
  }
  return max;
}

console.log(findMax([3, 7, 2, 9, 1]));   // 9
console.log(findMax([50, 20, 80, 10]));  // 80

ตัวอย่าง O(n): ค้นหาแบบ linear search

Linear search — O(n)JS

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

const nums = [15, 42, 8, 23, 4];

console.log(linearSearch(nums, 23));  // 3
console.log(linearSearch(nums, 99));  // -1

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

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

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

// ❌ อ่านที่ index ที่รู้ — O(1)
console.log(arr[0]);

// ❌ ซ้อน loop 2 ชั้น — O(n²)
for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length; j++) {
    console.log(arr[i], arr[j]);
  }
}

// ❌ ตัดครึ่งทุกรอบ — O(log n)
let n = arr.length;
while (n > 1) {
  n = Math.floor(n / 2);
}

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

O(n) — Linear Time

Operations ที่จำนวนขั้นตอนเติบโตตามสัดส่วนกับขนาดข้อมูล

O(n)

Single loop ผ่านทุก element

for, for...of, forEach ที่วิ่งจากต้นจนจบ array — จำนวนรอบ = n

O(n)

Linear search (indexOf, find, includes)

ไล่ดูทีละตัวจนเจอ — worst case ต้องดูทุกตัว

O(n)

หา max/min ใน unsorted array

ต้องตรวจทุกตัว เพราะถ้าข้ามอาจพลาดค่ามาก/น้อยสุด

O(n)

Sum / count / filter / map / reduce

ต้องเข้าถึงทุก element เพื่อคำนวณหรือสร้างผลลัพธ์

NOT O(n)

Array access by index / Object lookup by key

กระโดดไปยังตำแหน่งที่รู้ได้ทันที — เป็น O(1) ไม่ใช่ O(n)

NOT O(n)

Nested loops / ซ้อน 2 ชั้น

ทุกรอบของ loop นอก มี loop ในวิ่ง n รอบ — เป็น O(n²) ไม่ใช่ O(n)

Lab 1: นับจำนวนค่าที่ตรงกัน

Lab 2: หาค่ามากที่สุดใน array

Lab 3: ผลรวมของทุกตัวใน array

Lab 4: ค้นหาตำแหน่งของค่าใน array

Lab 5: กรองเฉพาะค่าที่ผ่านเงื่อนไข

Lab 6: นับจำนวนที่ผ่านเงื่อนไข

สรุป O(n) Operations

Operation	ตัวอย่าง	ความเร็ว
ไล่ทุกตัวใน array	for (const x of arr)	O(n)
indexOf / find / includes	arr.indexOf(5)	O(n)
หา max/min (unsorted)	findMax(arr)	O(n)
ผลรวม / นับ	sumAll(arr)	O(n)
filter / map / reduce	arr.filter(fn)	O(n)
Linear search	linearSearch(arr, x)	O(n)
อ่าน array ด้วย index	arr[0]	O(1) ❌
ซ้อน loop 2 ชั้น	for + for	O(n²) ❌

O(n) คืออะไร

ทำไม O(n) ถึงเติบโตเป็นเส้นตรง

ตัวอย่าง O(n): ไล่อ่านทุกตัวใน array

ตัวอย่าง O(n): หาค่าสูงสุด/ต่ำสุด

ตัวอย่าง O(n): ค้นหาแบบ linear search

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

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

O(n) — Linear Time

Single loop ผ่านทุก element

Linear search (indexOf, find, includes)

หา max/min ใน unsorted array

Sum / count / filter / map / reduce

Array access by index / Object lookup by key

Nested loops / ซ้อน 2 ชั้น

Lab 1: นับจำนวนค่าที่ตรงกัน

Lab 2: หาค่ามากที่สุดใน array

Lab 3: ผลรวมของทุกตัวใน array

Lab 4: ค้นหาตำแหน่งของค่าใน array

Lab 5: กรองเฉพาะค่าที่ผ่านเงื่อนไข

Lab 6: นับจำนวนที่ผ่านเงื่อนไข

สรุป O(n) Operations

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

O(n) — Linear Time

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

ทำไม findMax(arr) ใน unsorted array ถึงเป็น O(n)?

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

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

O(n) คืออะไร

ทำไม O(n) ถึงเติบโตเป็นเส้นตรง

ตัวอย่าง O(n): ไล่อ่านทุกตัวใน array

ตัวอย่าง O(n): หาค่าสูงสุด/ต่ำสุด

ตัวอย่าง O(n): ค้นหาแบบ linear search

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

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

O(n) — Linear Time

Single loop ผ่านทุก element

Linear search (indexOf, find, includes)

หา max/min ใน unsorted array

Sum / count / filter / map / reduce

Array access by index / Object lookup by key

Nested loops / ซ้อน 2 ชั้น

Lab 1: นับจำนวนค่าที่ตรงกัน

Lab 2: หาค่ามากที่สุดใน array

Lab 3: ผลรวมของทุกตัวใน array

Lab 4: ค้นหาตำแหน่งของค่าใน array

Lab 5: กรองเฉพาะค่าที่ผ่านเงื่อนไข

Lab 6: นับจำนวนที่ผ่านเงื่อนไข

สรุป O(n) Operations

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

O(n) — Linear Time

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

ทำไม findMax(arr) ใน unsorted array ถึงเป็น O(n)?

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

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

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