คุณเลือกโครงสร้างข้อมูลที่ถูกต้องสำหรับปัญหาได้อย่างไร

Question

Accepted Answer

เลือกโครงสร้างที่ **การดำเนินการที่บ่อยที่สุดมีราคาถูกที่สุด** สำหรับรูปแบบการเข้าถึงของคุณ เริ่มต้นด้วยการระบุการดำเนินการที่คุณจะทำ ประมาณความถี่ของพวกมัน จากนั้นจับคู่ให้สอดคล้องกับจุดแข็งของโครงสร้าง

## รายการตรวจสอบการตัดสินใจ

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## จับคู่การดำเนินการกับความซับซ้อน

| ความต้องการ | โครงสร้างที่ดีที่สุด | ค่าใช้งานหลักของการดำเนินการ |
|---|---|---|
| การเข้าถึงแบบสุ่มตามดัชนี | dynamic array | O(1) |
| ค้นหาตามคีย์ | hash map | O(1) เฉลี่ย |
| ที่เรียงลำดับ + การค้นหาช่วง | balanced BST | O(log n) |
| Min/max ซ้ำ ๆ | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| ค้นหาคำนำหน้า | trie | O(L) |

## ตัวอย่างการให้เหตุผล

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## เหตุใดนี่จึงมีความสำคัญ

การเลือกที่ถูกต้องมักเป็นความแตกต่างระหว่างโซลูชัน O(n) และ O(n²) — เลเวอร์ที่สำคัญที่สุดสำหรับประสิทธิภาพ

ผู้สัมภาษณ์ทดสอบการให้เหตุผลนี้อย่างแม่นยำ: พวกเขาต้องการเห็นว่าคุณแม็ปการดำเนินการกับต้นทุน ไม่ใช่เพียงแค่จดจำโครงสร้าง

ความต้องการ	โครงสร้างที่ดีที่สุด	ค่าใช้งานหลักของการดำเนินการ
การเข้าถึงแบบสุ่มตามดัชนี	dynamic array	O(1)
ค้นหาตามคีย์	hash map	O(1) เฉลี่ย
ที่เรียงลำดับ + การค้นหาช่วง	balanced BST	O(log n)
Min/max ซ้ำ ๆ	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
ค้นหาคำนำหน้า	trie	O(L)