On this page
เลือกโครงสร้างให้ถูก & ทบทวน Big-O
เลือก data structure ให้เหมาะกับงานคือทักษะจริง — ทบทวน Big-O แล้วดูตารางเทียบ
บทนี้คือหัวใจของคอร์ส — Data Structures & Algorithms เป็นพื้นฐานที่ทำให้เขียนโปรแกรมแก้ปัญหาได้ดีและมีประสิทธิภาพ หัวข้อแรกปูเรื่องการ "เลือกของให้ถูก" ซึ่งสำคัญกว่าการท่องสูตร
ทบทวน Big-O
Big-O บอกว่าเมื่อข้อมูลโตขึ้น เวลา/หน่วยความจำโตตามแค่ไหน — ดูที่ "อัตราการโต" ไม่ใช่เวลาจริง
| Big-O | ชื่อ | ตัวอย่าง |
|---|---|---|
| O(1) | คงที่ | เข้าถึง list[i], dict[key] |
| O(log n) | ลอการิทึม | binary search |
| O(n) | เชิงเส้น | วน list หนึ่งรอบ |
| O(n log n) | sort ที่ดี | |
| O(n²) | กำลังสอง | loop ซ้อน |
วิเคราะห์ Big-O ของโค้ดจริง (ลึกกว่าพื้นฐาน)
คอร์สพื้นฐานสอนให้รู้จัก Big-O แต่ละระดับ — ระดับนี้ต้อง "อ่านโค้ดแล้วบอก Big-O ได้เอง" หลักคือ: loop เดี่ยว = O(n), loop ซ้อน = คูณกัน, ตัวที่ไม่ขึ้นกับ n = ตัดทิ้ง เก็บเฉพาะพจน์ที่โตเร็วสุด
# O(n) — loop เดียว
for x in arr:
print(x)
# O(n²) — loop ซ้อน (n * n)
for i in arr:
for j in arr:
print(i, j)
# O(n) ไม่ใช่ O(2n) — ค่าคงที่ตัดทิ้ง
for x in arr: ... # n
for x in arr: ... # + n = 2n -> O(n)
# O(n + m) — คนละ input ห้ามยุบเป็น n
for x in arr_a: ... # n
for y in arr_b: ... # mbest / average / worst case
อัลกอริทึมเดียวอาจมีหลายกรณี — มักสนใจ worst case (รับประกันแย่สุด) แต่บางทีดู average ด้วย เช่น hash table เฉลี่ย O(1) แต่ worst O(n) เมื่อ collision เยอะ
amortized — เฉลี่ยระยะยาว
บาง operation บางครั้งแพง บางครั้งถูก แต่เฉลี่ยแล้วถูก เช่น list.append() ปกติ O(1) แต่บางครั้งต้องขยายหน่วยความจำ (แพง) เฉลี่ยทั้งหมดยังเป็น O(1) เรียกว่า amortized O(1) — เข้าใจจุดนี้ช่วยไม่ตื่นตระหนกกับ worst case ที่นาน ๆ เกิดที
นอกจากเวลา ต้องดูหน่วยความจำด้วย เช่น สร้าง list ใหม่ขนาด n = O(n) space; recursion ลึก n ชั้น = O(n) space จาก call stack (เจอในหัวข้อ recursion) — บางครั้งแลกเวลาเร็วขึ้นด้วย memory ที่มากขึ้น (time-space tradeoff)
ตารางเทียบ: operation ↔ structure
นี่คือตารางที่ควรเข้าใจ — ไม่ต้องท่อง แต่ให้รู้ว่า "งานแบบไหนใช้อะไรเร็ว"
| operation | list | dict/set | deque |
|---|---|---|---|
| เข้าถึงด้วย index | O(1) | — | O(n) |
| ค้นหาค่า (in) | O(n) | O(1) | O(n) |
| เพิ่ม/ลบท้าย | O(1) | O(1) | O(1) |
| เพิ่ม/ลบหัว | O(n) | — | O(1) |
ถ้าต้อง "ค้นหาบ่อย" → ใช้ set/dict (O(1)) ไม่ใช่ list (O(n)); ถ้าต้อง "เพิ่ม/ลบหัวแถวบ่อย" → ใช้ deque ไม่ใช่ list การเลือกถูกตั้งแต่ต้นมักเร็วกว่าการ optimize ทีหลังมาก (เชื่อมบท Performance)
เสริม: bit manipulation เบื้องต้น (สำหรับคนสนใจ)
บางโจทย์ใช้การจัดการระดับ bit ได้กระชับ เช่น เช็คเลขคู่ด้วย n & 1, คูณ/หาร 2 ด้วย shift
print(5 & 1) # 1 (คี่) ; 4 & 1 = 0 (คู่)
print(3 << 1) # 6 (คูณ 2)
print(8 >> 1) # 4 (หาร 2)
print(5 | 2) # 7 (OR) ; 5 & 3 = 1 (AND)สรุปหัวข้อนี้
- อ่านโค้ดแล้วบอก Big-O เองได้: loop ซ้อน = คูณ, คงที่ตัดทิ้ง, เก็บพจน์โตเร็วสุด
- best/average/worst case + amortized (list.append O(1) เฉลี่ย)
- ค้นหาบ่อย → set/dict (O(1)); เพิ่ม/ลบหัว → deque (O(1)) ไม่ใช่ list
- เลือก DS ถูกตั้งแต่ต้นสำคัญกว่าการ optimize ทีหลัง; ดู space ด้วย
1) มีงานต้องเช็คว่า user_id ซ้ำไหมในข้อมูลล้านแถว — เลือก DS ไหน เพราะอะไร 2) ต้องทำคิวงานเข้าก่อนออกก่อน — ใช้อะไร 3) บอก Big-O ของการค้น in list กับ in set 4) ลอง bit ops: เช็คคู่/คี่ด้วย & 1