สรุปขั้นตอนวิธี

หน้าอ้างอิงแบบสแกนง่าย พร้อมนำไปฉายสอนได้ทันที รวมขั้นตอนวิธีและกระบวนทัศน์การออกแบบทั้งหมดที่หลักสูตรครอบคลุม ใช้หน้านี้เพื่อค้นคำตอบระหว่างสัมภาษณ์งานหรือระหว่างบรรยาย — หากต้องการเวอร์ชันสอนแบบละเอียดของแถวไหน ให้ตามลิงก์ในแถวนั้น

ข้อคิดสำคัญที่สุด: การเลือกขั้นตอนวิธีเกือบทุกครั้งคือการแลกเปลี่ยนกันระหว่างสามแกน — เวลา, หน่วยความจำ, และ การรับประกัน (เสถียรภาพ? in-place? มีขอบเขต worst-case ที่แน่นอนหรือไม่?) การท่องจำชื่อไม่มีประโยชน์ — การจำว่า แกนไหนที่คุณกำลังยอมเสียไป ต่างหากคือทักษะทั้งหมด

Big O แบบเร็ว

สัญกรณ์	ชื่อ	ข้อมูล 1,000,000 ตัว ใช้ประมาณ	ตัวอย่าง
`O(1)`	คงที่	1 ก้าว	ค้นหาในตารางแฮช, เข้าถึงอาเรย์ด้วยดัชนี
`O(log n)`	ลอการิทึม	~20 ก้าว	การค้นหาแบบทวิภาค, ความสูงของต้นไม้สมดุล
`O(n)`	เชิงเส้น	1,000,000 ก้าว	สแกนทีละตัว, ลูปเดียว
`O(n log n)`	เชิงเส้น-ลอการิทึม	~20,000,000 ก้าว	merge sort, heap sort, Timsort
`O(n²)`	กำลังสอง	10¹² ก้าว	ลูปซ้อน, bubble/selection/insertion sort
`O(2ⁿ)`	เอ็กซ์โพเนนเชียล	มหาศาลจนไม่สมเหตุสมผล	fibonacci เรียกซ้ำแบบไร้เดียงสา, brute-force หา subset ทั้งหมด
`O(n!)`	แฟกทอเรียล	ไม่มีวันเสร็จ	brute-force travelling salesman

ตารางหลัก — การค้นหา

ขั้นตอนวิธี	ดีที่สุด	เฉลี่ย	แย่ที่สุด	หน่วยความจำ	เงื่อนไข	เวลาที่ควรใช้
การค้นหาเชิงเส้น	`O(1)`	`O(n)`	`O(n)`	`O(1)`	ไม่มี	ข้อมูลยังไม่เรียง หรือค้นหาแค่ครั้งเดียวจนไม่คุ้มที่จะเรียงก่อน
การค้นหาแบบทวิภาค	`O(1)`	`O(log n)`	`O(log n)`	`O(1)` แบบวนซ้ำ	ข้อมูลต้องเรียงแล้ว	ข้อมูลเรียงอยู่แล้ว (หรือเรียงครั้งเดียวแล้วค้นหาซ้ำหลายครั้ง)

ตารางหลัก — การจัดเรียง

ขั้นตอนวิธี	ดีที่สุด	เฉลี่ย	แย่ที่สุด	หน่วยความจำ	เสถียร?	in-place?	เวลาที่ควรใช้
Bubble sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	ใช่	ใช่	ใช้สอนเท่านั้น — ไม่ใช้ในโปรดักชันเด็ดขาด
Selection sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	ไม่	ใช่	ลดจำนวนการ สลับค่า ให้น้อยที่สุด — มีประโยชน์เมื่อการเขียนมีต้นทุนสูง (เช่น flash memory)
Insertion sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	ใช่	ใช่	ข้อมูล `n` น้อย หรือข้อมูลที่ เกือบเรียงอยู่แล้ว — นี่คือเหตุผลที่ Timsort ใช้มันเป็น subroutine
Merge sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	ใช่	ไม่	รับประกัน `O(n log n)` เสมอไม่ว่ากรณีใด — สำคัญมากสำหรับระบบเรียลไทม์และลิงก์ลิสต์
Quicksort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	ไม่	ใช่	เร็วที่สุด ในทางปฏิบัติ สำหรับอาเรย์ที่มี cache locality ดี — ค่าเริ่มต้นภายในไลบรารีหลายตัว
Heap sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	ไม่	ใช่	รับประกัน `O(n log n)` และ หน่วยความจำ `O(1)` — เมื่อไม่มีอาเรย์พิเศษให้เผื่อแบบ merge sort
Timsort	`O(n)`	`O(n log n)`	`O(n log n)`	`O(n)`	ใช่	ไม่	สิ่งที่ `sorted()` ของ Python และ `Arrays.sort()` สำหรับ object ใน Java ใช้จริง — ผสม merge + insertion sort เพื่อใช้ประโยชน์จาก run ที่เรียงอยู่แล้วในข้อมูล

ข้อคิดสำคัญที่สุด: O(n log n) คือ ขอบเขตล่างที่พิสูจน์แล้ว สำหรับการจัดเรียงแบบเปรียบเทียบใดๆ (CLRS พิสูจน์ด้วยแนวคิด decision-tree) ถ้าเห็นใครอ้างว่ามี comparison sort ที่ O(n) นั่นคือบั๊ก ไม่ใช่นวัตกรรม ส่วนการจัดเรียงที่ไม่เปรียบเทียบ (counting sort, radix sort) เอาชนะ O(n log n) ได้ — แต่ต้องอาศัยโครงสร้างพิเศษของข้อมูล (ช่วงตัวเลขจำกัด, จำนวนหลักคงที่)

ตารางหลัก — กราฟ

ขั้นตอนวิธี	เวลา	หน่วยความจำ	ตอบคำถามอะไร	เวลาที่ควรใช้
BFS (การค้นหาแบบกว้างก่อน)	`O(V + E)`	`O(V)`	เส้นทางสั้นที่สุดในกราฟ ไม่มีน้ำหนัก; ชั้นแบบ level-order	คำถามประเภท “น้อยขั้นที่สุด” — ระดับความห่างในโซเชียลเน็ตเวิร์ก, เส้นทางสั้นสุดแบบไม่มีน้ำหนัก
DFS (การค้นหาแบบลึกก่อน)	`O(V + E)`	`O(V)`	การเข้าถึงได้ (reachability), ตรวจวงจร, ลำดับทอพอโลจี, กลุ่มเชื่อมต่อ	สำรวจเขาวงกต, ตรวจวงจร, หรือใช้เป็นส่วนประกอบของขั้นตอนวิธีกราฟอื่น
Dijkstra’s algorithm	`O((V + E) log V)` เมื่อใช้ binary heap	`O(V)`	เส้นทางสั้นที่สุดในกราฟ มีน้ำหนัก ที่น้ำหนักไม่ติดลบ	เส้นทาง GPS, การจัดเส้นทางเครือข่าย — ปัญหา “เส้นทางถูกที่สุด” ที่ไม่มีน้ำหนักติดลบ
Topological sort	`O(V + E)`	`O(V)`	ลำดับเชิงเส้นที่ถูกต้องของ DAG (กราฟมีทิศทางไม่มีวงจร)	ระบบ build, เงื่อนไขวิชาก่อน, การจัดตารางงาน — “อะไรต้องเกิดก่อนอะไร”

กับดักที่พบบ่อย: ทั้ง BFS และ DFS ใช้เวลา O(V + E) เท่ากัน — ความต่างไม่เคยอยู่ที่ความเร็ว แต่อยู่ที่ ลำดับการเยือนปม และ คำถามอะไรที่ลำดับนั้นตอบได้ ใช้ BFS เมื่อ “สั้นที่สุด” สำคัญ; ใช้ DFS เมื่อ “มีเส้นทางอยู่หรือไม่” หรือ “โครงสร้างเป็นอย่างไร” สำคัญกว่า

ตารางหลัก — กระบวนทัศน์การออกแบบ

กระบวนทัศน์	แนวคิดหลัก	ความซับซ้อนทั่วไป	รับประกันคำตอบดีที่สุดหรือไม่?	เวลาที่ควรใช้
Brute force	ลองทุกความเป็นไปได้	มักเป็นเอ็กซ์โพเนนเชียลหรือแฟกทอเรียล	ใช่ (ด้วยการลองหมด)	ใช้เป็นฐานตรวจความถูกต้อง; `n` เล็ก; ต้องการคำตอบอ้างอิงเพื่อทดสอบขั้นตอนวิธีที่เร็วกว่า
แบ่งแยกและพิชิต	แบ่งเป็นปัญหาย่อยโครงสร้างเดียวกัน แล้วรวมผลลัพธ์	มักเป็น `O(n log n)` (ดู Master Theorem)	ใช่ ถ้า base case และขั้นตอนรวมถูกต้อง	ปัญหาแบ่งได้สะอาด และปัญหาย่อยไม่ทับซ้อนกัน — merge sort, การค้นหาแบบทวิภาค, quicksort
Greedy	เลือกทางที่ดีที่สุด ณ ขณะนั้น แล้วไม่ย้อนกลับมาแก้ไข	มักเป็น `O(n log n)` (ส่วนใหญ่มาจากการเรียงข้อมูล)	เฉพาะเมื่อปัญหามีคุณสมบัติ greedy-choice property เท่านั้น	Activity selection, Huffman coding, Dijkstra — ต้องพิสูจน์ว่า greedy ถูกต้องก่อนเสมอ (exchange argument) อย่าเดาเอาเอง
Dynamic Programming	จำผลลัพธ์ปัญหาย่อยที่ซ้อนทับไว้ใช้ซ้ำ	มักลดจาก `O(2ⁿ)` เหลือ `O(n)` หรือ `O(n²)`	ใช่ ถ้าปัญหามี optimal substructure	ปัญหาย่อยซ้อนทับ + optimal substructure — Fibonacci, knapsack, edit distance, longest common subsequence
Backtracking	สร้างคำตอบทีละขั้น แล้ว “ตัด” กิ่งที่รู้ทันทีว่าใช้ไม่ได้	worst case เป็นเอ็กซ์โพเนนเชียล แต่การตัดกิ่งลดต้นทุนจริงลงมาก	ใช่ (สำรวจทุกกิ่งที่เป็นไปได้)	ปัญหาข้อจำกัด — N-Queens, Sudoku, การสร้าง permutation/subset

วิธีแยก greedy จาก DP ตอนสัมภาษณ์: ถามตัวเองว่า “การเลือกตอนนี้ขึ้นกับการเลือกที่ยังไม่เกิดขึ้นหรือไม่ หรือการเลือกช่วงแรกสองแบบที่ต่างกันจะนำไปสู่ปัญหาย่อยเดียวกันได้หรือไม่” ถ้าปัญหาย่อยทับซ้อนกัน นั่นคือ DP ถ้าทางเลือกที่ดีที่สุดในตอนนั้นปลอดภัยเสมอและไม่ต้องย้อนมาแก้ นั่นคือ greedy หากไม่แน่ใจ DP คือทางเลือกที่ปลอดภัยกว่า — greedy ที่ไม่มีการพิสูจน์ความถูกต้องคือบั๊กที่รอวันถูกจับได้ ไม่ว่าจะโดยผู้ตรวจโค้ดที่เป็นคนหรือ AI

ผังการตัดสินใจเลือกขั้นตอนวิธี

ข้อมูลเรียงอยู่แล้วหรือเรียงได้ครั้งเดียวไหวไหม? → การค้นหาแบบทวิภาคชนะการค้นหาเชิงเส้นทุกครั้งหลังจากนั้น
ต้องการการรับประกัน worst case หรือไม่ (ระบบเรียลไทม์ หรือ input ที่ถูกออกแบบมาให้แย่)? → merge sort หรือ heap sort ไม่ใช่ quicksort
กราฟมีน้ำหนักหรือไม่? → ถ้ามีใช้ Dijkstra ถ้าไม่มีน้ำหนัก → BFS ง่ายกว่าและถูกต้องเท่ากัน
ปัญหาย่อยทับซ้อนกันหรือไม่? → dynamic programming ถ้าไม่ทับซ้อนแต่แบ่งได้สะอาด → แบ่งแยกและพิชิต
ทางเลือกที่ดีที่สุด ณ ตอนนี้ ไม่มีวันต้องย้อนกลับมาแก้โดยไม่เสียความถูกต้องใช่ไหม? → พิสูจน์ก่อน แล้วค่อยใช้ greedy
พื้นที่ค้นหาเล็กและมีข้อจำกัดต้องเป็นไปตามทุกข้อหรือไม่? → backtracking
ไม่เข้าข้อไหนเลย และความถูกต้องสำคัญกว่าความเร็วตอนนี้? → brute force ก่อน แล้วค่อยปรับให้เร็วขึ้นเมื่อพิสูจน์ว่าถูกต้องแล้ว

แผนที่ช่วงการอบรม

ขั้นตอนวิธี / เทคนิค	แนวคิดสำคัญ	ความซับซ้อนเด่น	ช่วง
การวิเคราะห์ Big O	เครื่องมือกลางสำหรับประเมินต้นทุน	—	๑.๓ และต่อเนื่อง
การค้นหาเชิงเส้น	ตรวจทีละตัวจนพบ	`O(n)`	๓.๑
การค้นหาแบบทวิภาค	แบ่งครึ่งช่วง — ข้อมูลต้องเรียงแล้ว	`O(log n)`	๓.๑
การจัดเรียง	จัดเรียงเชิงเปรียบเทียบ เน้นต้นทุน/เสถียรภาพ	`O(n log n)` เป็นขีดจำกัด	๓.๑
การท่องต้นไม้	เยือนปมตามลำดับก่อน/กลาง/หลัง	`O(n)`	๒.๓
การเรียกซ้ำ / แบ่งแยกพิชิต	แบ่งเป็นปัญหาย่อยโครงสร้างเดียวกัน	ขึ้นกับโครงสร้างการเรียก	๓.๒
DP / Memoization	ใช้ผลปัญหาย่อยที่ซ้อนทับ ลดการคำนวณซ้ำ	ลดจาก `O(2ⁿ)` เหลือ `O(n)` ได้ในหลายกรณี	๓.๓
BFS / DFS	สำรวจกราฟอย่างเป็นระบบ	`O(V + E)`	๓.๓

หมายเหตุ: กราฟ การท่องกราฟ และ DP นำเสนอ “เชิงแนวคิด” ในหลักสูตรนี้ — เน้นความเข้าใจหลักการและการประเมินคุณภาพของโซลูชัน ไม่ได้เน้นท่องจำบทพิสูจน์ทุกข้อ

เจาะลึกเพิ่มเติม

CLRS (Cormen, Leiserson, Rivest, Stein), Introduction to Algorithms, 4th ed. — ตำราอ้างอิงมาตรฐานของทุกขั้นตอนวิธีในหน้านี้; บทที่ 6–9 สำหรับการจัดเรียง, บทที่ 15 สำหรับ DP, บทที่ 22–24 สำหรับกราฟ
Skiena, The Algorithm Design Manual, 3rd ed. — ให้สัญชาตญาณ “เทคนิคไหนใช้เมื่อไร” ดีที่สุด พร้อมเรื่องเล่าจากงานจริงที่เลือกผิดแล้วพัง
Sedgewick & Wayne, Algorithms, 4th ed. — โค้ดตัวอย่างที่สะอาดและผ่านการทดสอบ พร้อมเปรียบเทียบประสิทธิภาพจริงของการจัดเรียงและกราฟทุกตัวในหน้านี้
Kleinberg & Tardos, Algorithm Design — แหล่งที่ดีที่สุดสำหรับ พิสูจน์ ว่า greedy ถูกต้อง (exchange argument) และฝึกวินัยในการตั้งสมการ DP
Roughgarden, Algorithms Illuminated (4 เล่ม) — เข้าใจง่ายแต่ยังคงความเข้มงวด เข้าคู่ได้ดีกับ Stanford CS161 โดยเฉพาะเรื่อง Master Theorem สำหรับแบ่งแยกและพิชิต
Big-O Cheat Sheet — ชีทสรุปความซับซ้อนหน้าเดียวที่ใช้เช็คไขว้กับหน้านี้ได้อย่างรวดเร็ว