Big-O Notation
O(1) — Constant Time
เรียนรู้ O(1) Constant Time — operations ที่ใช้เวลาคงที่ไม่ว่าข้อมูลจะใหญ่แค่ไหน พร้อม 6 Labs ฝึกเขียน array access, object lookup, push/pop, swap, และ nested object access
O(1) คืออะไร
O(1) หรือ **Constant Time** หมายความว่า ไม่ว่าข้อมูลจะมีขนาดใหญ่แค่ไหน (n เท่าไหร่) เวลาที่ใช้ทำงานจะ **คงที่เสมอ** — คือ 1 ขั้นตอน หรือจำนวนขั้นตอนที่ไม่เปลี่ยนแปลงตาม n
ลองนึกภาพ: คุณมีตู้ลิ้นชัก 100 ใบ แต่ละใบมีป้ายบอกหมายเลข ถ้าคุณรู้หมายเลขลิ้นชัก คุณดึงลิ้นชักนั้นได้ทันที ไม่ว่าจะมีลิ้นชัก 10 ใบหรือ 10,000 ใบ ก็ใช้เวลาเท่ากัน — นี่คือ O(1)
ตัวอย่าง O(1): อ่านอาเรย์ตาม index
JavaScript Array เก็บข้อมูลต่อเนื่องใน memory เมื่อเรารู้ index เราสามารถกระโดดไปยังตำแหน่งนั้นได้ทันที เพราะ engine คำนวณตำแหน่ง memory จาก `base + index × size` ได้เลย — ไม่ต้องวิ่งผ่านช่องอื่น
ทั้ง **อ่าน** และ **เขียน** ที่ตำแหน่ง index ที่รู้อยู่แล้ว ใช้เวลาคงที่ เพราะเป็นการคำนวณตำแหน่ง memory ตรงๆ
ตัวอย่าง O(1): อ่าน/เขียนค่าจาก Object
Object ใน JavaScript ใช้ **hash table** เก็บ property เมื่อเราเข้าถึง property ด้วย key เช่น `obj.name` หรือ `obj["name"]` engine จะ hash key นั้นแล้วกระโดดไปยังตำแหน่งที่เก็บค่าได้ทันที — ไม่ต้องไล่ตรวจทุก property
ในทางปฏิบัติ JavaScript engine ทำให้การเข้าถึง Object property ด้วย key เป็น O(1) โดยเฉลี่ย — เร็วพอที่จะถือว่าเป็น constant time
ตัวอย่าง O(1): push และ pop
`push()` เพิ่มค่าที่ท้าย array และ `pop()` ลบค่าที่ท้าย array — ทั้งสองอย่างทำงานโดยตรงที่ตำแหน่งสุดท้าย ไม่ต้องย้ายข้อมูลช่องอื่น
เรียกว่า **amortized O(1)** เพราะส่วนใหญ่ใช้เวลาคงที่ แต่บางครั้งเมื่อ array ต้องขยายพื้นที่ใน memory อาจใช้เวลามากขึ้นชั่วขณะ อย่างไรก็ตาม เมื่อเฉลี่ยกันหลายๆ ครั้ง ก็ถือว่าเป็น O(1)
สิ่งที่ **ไม่ใช่** O(1)
เข้าใจผิดบ่อยที่สุดคือ คิดว่าทุก operation บน array เป็น O(1) ความจริงคือ **ถ้าต้องไล่ตรวจหรือย้ายข้อมูลหลายช่อง มันไม่ใช่ O(1)**
กฎง่ายๆ: **ถ้า operation นั้นต้อง "ไล่" หรือ "ย้าย" ข้อมูลเป็นจำนวนที่ขึ้นกับ n แสดงว่าไม่ใช่ O(1)**
กฎสำคัญ: O(1) Operations
O(1) — Constant Time
Operations ที่ใช้เวลาคงที่ ไม่ว่าข้อมูลจะมีขนาดเท่าไหร่
Array access/update by index
อ่านหรือเขียนค่าที่ตำแหน่ง index ที่รู้อยู่ เช่น arr[3] หรือ arr[0] = 99
Object/Map lookup by key
เข้าถึง property ด้วย key เช่น obj.name หรือ obj["city"] — hash-based lookup
push/pop ที่ท้าย array
เพิ่มหรือลบที่ตำแหน่งสุดท้าย — ไม่ต้องย้ายข้อมูลช่องอื่น (amortized)
การดำเนินการทางคณิตศาสตร์
บวก ลบ คูณ หาร เปรียบเทียบค่า — ใช้เวลาคงที่สำหรับค่าตัวเลขปกติ
indexOf, find, includes, unshift, splice กลาง array
ต้องไล่ตรวจหรือย้ายข้อมูล — ไม่ใช่ O(1) แต่เป็น O(n) หรือมากกว่า
Lab 1: อ่านค่าจากอาเรย์ด้วย index
Lab 2: อ่านค่าจาก Object ด้วย key
Lab 3: แก้ไขค่าในอาเรย์ที่ตำแหน่งที่รู้
Lab 4: เพิ่มและลบท้ายอาเรย์ด้วย push/pop
Lab 5: สลับค่าสองตำแหน่งในอาเรย์
Lab 6: ดึงข้อมูลจาก nested object
สรุป O(1) Operations
| Operation | ตัวอย่าง | ความเร็ว |
|---|---|---|
| อ่าน array ด้วย index | arr[3] | O(1) |
| เขียน array ด้วย index | arr[0] = 99 | O(1) |
| อ่าน Object property | menu.pizza | O(1) |
| เขียน Object property | obj.key = val | O(1) |
| push (เพิ่มท้าย array) | arr.push(x) | O(1)* |
| pop (ลบท้าย array) | arr.pop() | O(1)* |
| สลับค่า 2 ตำแหน่ง | swap(arr, i, j) | O(1) |
| indexOf / find / includes | arr.indexOf(x) | O(n) ❌ |
| unshift / splice กลาง | arr.unshift(x) | O(n) ❌ |
ทบทวนความเข้าใจ
O(1) — Constant Time
ทดสอบความเข้าใจเกี่ยวกับ O(1) operations