02 · Algorithms & Data Structures
02 · อัลกอริทึมและโครงสร้างข้อมูล
This chapter is the floor immediately above computability: 01 says a task can be done at all, and this floor asks what doing it will cost.
ชั้นนี้วางอยู่เหนือเรื่องคำนวณได้ (computability) ขึ้นมาหนึ่งชั้นพอดี — บทที่ 01 บอกว่างานหนึ่งทำได้หรือไม่ ชั้นนี้ถามว่าทำแล้วเสียต้นทุนเท่าไร
Given that it can be computed, how well can it be done?
ในเมื่อคำนวณได้แล้ว จะทำได้ดีแค่ไหน
In 1960, at a seminar he was running at Moscow State University, Andrey Kolmogorov told the room that multiplying two n-digit numbers must cost on the order of n² elementary operations — that the method every schoolchild learns, digit against digit, is essentially the best there is. It was a reasonable thing to believe. Every multiplication algorithm anyone had written behaved that way, and Kolmogorov was not a man whose conjectures were casually wrong.
ปี 1960 ในสัมมนาที่เขาเป็นผู้นำที่มหาวิทยาลัยมอสโก Andrey Kolmogorov บอกกับคนทั้งห้องว่า การคูณเลข n หลักสองจำนวนต้องเสียต้นทุนราว n² ครั้งของการกระทำพื้นฐาน วิธีที่เด็กนักเรียนทุกคนเรียนกัน คูณหลักต่อหลัก คือวิธีที่ดีที่สุดเท่าที่จะมีได้ ความเชื่อนี้มีเหตุผลรองรับ อัลกอริทึม (algorithm) การคูณทุกตัวที่เคยมีคนเขียนขึ้นมาล้วนทำงานแบบนั้น และข้อคาดการณ์ของ Kolmogorov ก็ไม่ใช่ของที่ผิดกันง่ายๆ
A student in the room, Anatoly Karatsuba, broke it inside a week. His trick is almost embarrassingly small: cut each number in half. The schoolbook method then wants four half-sized products; Karatsuba noticed that three suffice, because the fourth quantity can be recovered by subtracting the ones you already have. Do that recursively and the cost falls from n² to n^log₂3 — about n^1.585. At the next meeting Kolmogorov reported the refutation himself, and then discontinued the seminar (Karatsuba, The Complexity of Computations, 1995).
นักศึกษาในห้องคนหนึ่งชื่อ Anatoly Karatsuba หักล้างมันได้ภายในสัปดาห์เดียว กลเม็ดของเขาเล็กจนน่าอาย คือตัดเลขแต่ละจำนวนออกเป็นครึ่ง วิธีแบบตำราต้องใช้ผลคูณขนาดครึ่งถึงสี่ตัว Karatsuba เห็นว่าสามตัวก็พอ เพราะตัวที่สี่หาได้จากการลบตัวที่มีอยู่แล้วออกจากกัน ทำแบบนี้ซ้ำลงไปเรื่อยๆ (recursion) ต้นทุนลดจาก n² เหลือ n^log₂3 หรือราว n^1.585 การประชุมครั้งถัดมา Kolmogorov รายงานข้อหักล้างนั้นด้วยตัวเอง แล้วปิดสัมมนาไปเลย (Karatsuba, The Complexity of Computations, 1995)
Nothing in the world had changed that week. No new machine, no new physics. A fact about cost had been discovered, the way facts about nature are discovered — and that is what this floor studies.
โลกไม่ได้เปลี่ยนไปเลยในสัปดาห์นั้น ไม่มีเครื่องใหม่ ไม่มีฟิสิกส์ใหม่ สิ่งที่ถูกค้นพบคือข้อเท็จจริงเกี่ยวกับ ต้นทุน ค้นพบในแบบเดียวกับที่คนค้นพบข้อเท็จจริงเกี่ยวกับธรรมชาติ — และนี่คือสิ่งที่ชั้นนี้ศึกษา
Cost is a shape, not a number. The notation for it was borrowed from number theory: Paul Bachmann introduced big-O in 1894, and Edmund Landau adopted it in 1909, crediting him (MAA Convergence); Donald Knuth's 1976 note in SIGACT News pushed computing to standardize on O, Ω and Θ (Knuth, 1976). Notice what the notation deliberately throws away: constant factors. That is not sloppiness. Constants are the part of the cost that hardware, compilers, and careful coding can move; the growth rate is the part the algorithm itself owns, and no amount of engineering below it will change it. A machine ten times faster buys you a constant. An exponent buys you the future: on Karatsuba's exponents alone, the saving is roughly eighteen-fold at a thousand digits and three hundred-fold at a million.
ต้นทุนเป็นรูปทรง ไม่ใช่ตัวเลข สัญกรณ์ที่ใช้แทนมันยืมมาจากทฤษฎีจำนวน Paul Bachmann เสนอ Big-O ครั้งแรกในปี 1894 Edmund Landau รับมาใช้ต่อในปี 1909 พร้อมให้เครดิตเขา (MAA Convergence) บันทึกของ Donald Knuth ในปี 1976 ใน SIGACT News ผลักให้วงการคอมพิวเตอร์ยึด O, Ω และ Θ เป็นมาตรฐานเดียวกัน (Knuth, 1976) สังเกตสิ่งที่สัญกรณ์นี้ตั้งใจโยนทิ้ง คือค่าคงที่ นั่นไม่ใช่ความมักง่าย ค่าคงที่คือส่วนของต้นทุนที่ฮาร์ดแวร์ คอมไพเลอร์ และการเขียนโค้ดอย่างระมัดระวังยังขยับได้ ส่วน อัตรา การเติบโตเป็นของอัลกอริทึมเอง วิศวกรรมชั้นล่างเท่าไรก็เปลี่ยนมันไม่ได้ เครื่องที่เร็วขึ้นสิบเท่าซื้อค่าคงที่ให้คุณ เลขชี้กำลังซื้ออนาคตให้คุณ เฉพาะเลขชี้กำลังของ Karatsuba อย่างเดียวก็ประหยัดได้ราวสิบแปดเท่าที่พันหลัก และสามร้อยเท่าที่ล้านหลัก
A small catalogue of strategies covers most of the ground. They are worth knowing by name, because almost every algorithm you will meet is one of them wearing local clothes.
กลยุทธ์ไม่กี่ข้อครอบคลุมสนามนี้ไว้เกือบทั้งหมด คุ้มที่จะจำไว้ทีละชื่อ เพราะแทบทุกอัลกอริทึมที่คุณจะเจอ คือหนึ่งในนี้ที่สวมเสื้อผ้าเฉพาะถิ่นเข้ามา
Divide and conquer splits a problem into smaller copies of itself, solves those, and stitches the answers together — Karatsuba's trick, and mergesort, which von Neumann wrote out in 1945 in what survives as the earliest example of his coding (Knuth, "Von Neumann's First Computer Program," 1970). Its most famous application is a three-page paper by Volker Strassen with the flatly provocative title "Gaussian elimination is not optimal," which multiplied matrices in about n^2.807 instead of n³ (Numerische Mathematik 13, 1969). The chase it started has run for over half a century and is still running: the published record now stands near n^2.371 (Alman et al., SODA 2025), and nobody knows how far down it goes.
แบ่งแล้วพิชิต (divide and conquer) แยกปัญหาออกเป็นสำเนาย่อยของตัวเอง แก้ทีละชิ้น แล้วเย็บคำตอบกลับเข้าด้วยกัน กลเม็ดของ Karatsuba เป็นแบบนี้ mergesort ก็เช่นกัน von Neumann เขียนมันไว้ในปี 1945 และเหลือรอดมาเป็นตัวอย่างการเขียนโค้ดชิ้นแรกสุดของเขา (Knuth, "Von Neumann's First Computer Program," 1970) การประยุกต์ใช้ที่ดังที่สุดคือเปเปอร์สามหน้าของ Volker Strassen ตั้งชื่อยั่วยุตรงๆ ว่า "Gaussian elimination is not optimal" คูณเมทริกซ์ (matrix multiplication) ได้ในราว n^2.807 แทน n³ (Numerische Mathematik 13, 1969) การไล่ล่าที่มันจุดชนวนไว้ดำเนินมากว่าครึ่งศตวรรษและยังไม่จบ สถิติที่ตีพิมพ์ตอนนี้อยู่ราว n^2.371 (Alman et al., SODA 2025) และไม่มีใครรู้ว่ามันลงไปได้ลึกแค่ไหน
The greedy strategy takes the locally best step and never looks back — either naive or optimal, depending entirely on whether the problem has the structure that rewards it — and when it does, greed is unbeatable. Dijkstra's shortest-path algorithm is the canonical case, published in three pages in 1959 (Numerische Mathematik 1: 269–271). He designed it, by his own account, in about twenty minutes in 1956, without pencil or paper, sitting on a café terrace in Amsterdam while out shopping with his fiancée (oral history, Charles Babbage Institute, 2001).
กลยุทธ์ greedy คว้าก้าวที่ดีที่สุดตรงหน้าแล้วไม่หันกลับไปมองอีก จะไร้เดียงสาหรือเหมาะที่สุด ขึ้นอยู่กับว่าโจทย์มีโครงสร้างที่ตอบแทนวิธีนี้หรือไม่ล้วนๆ และเมื่อโจทย์มี greedy ก็เอาชนะไม่ได้เลย อัลกอริทึมหาเส้นทางสั้นสุดของ Dijkstra คือตัวอย่างคลาสสิก ตีพิมพ์ในสามหน้าเมื่อปี 1959 (Numerische Mathematik 1: 269–271) ตามคำบอกเล่าของเขาเอง เขาคิดมันขึ้นมาในราวยี่สิบนาทีเมื่อปี 1956 ไม่มีดินสอ ไม่มีกระดาษ นั่งอยู่ที่ระเบียงคาเฟ่ในอัมสเตอร์ดัมระหว่างออกไปช็อปปิ้งกับคู่หมั้น (oral history, Charles Babbage Institute, 2001)
When subproblems repeat, dynamic programming says to remember rather than recompute. Richard Bellman developed it at RAND, where he worked from 1948 to 1965, and the name is a deliberate disguise: RAND answered to a Secretary of Defense who, in Bellman's telling, "had a pathological fear and hatred of the word research," so he chose two words nobody could object to (Dreyfus, "Richard Bellman on the Birth of Dynamic Programming," Operations Research 50, no. 1, 2002). The technique is more honest than its name — it is simply the trade of memory for time.
เมื่อโจทย์ย่อยเกิดซ้ำ dynamic programming สั่งให้จำไว้ ไม่ใช่คำนวณใหม่ Richard Bellman พัฒนามันขึ้นที่ RAND ที่ซึ่งเขาทำงานอยู่ตั้งแต่ปี 1948 ถึง 1965 ชื่อนี้เป็นการอำพรางที่ตั้งใจ RAND ขึ้นตรงกับรัฐมนตรีกลาโหมที่ตามคำบอกเล่าของ Bellman "กลัวและเกลียดคำว่า research อย่างผิดปกติ" เขาจึงหยิบสองคำที่ไม่มีใครค้านได้มาใช้แทน (Dreyfus, "Richard Bellman on the Birth of Dynamic Programming," Operations Research 50, no. 1, 2002) ตัวเทคนิคซื่อตรงกว่าชื่อของมัน มันคือการแลกหน่วยความจำเอาเวลากลับมา เท่านั้นเอง
Strangest of the four is randomization, which wins by refusing to be predictable. Tony Hoare devised Quicksort in 1959–60 as a student in Moscow, working on machine translation of Russian, and published it in 1962 (The Computer Journal 5, no. 1: 10–16). Its worst case is quadratic and an adversary who knows your rule can force it every time; choose the pivot at random and that adversary is disarmed, because now they would have to guess your dice.
แปลกที่สุดในสี่กลยุทธ์นี้คือ การสุ่ม (randomization) ที่ชนะด้วยการไม่ยอมให้ใครทายทางถูก Tony Hoare คิด Quicksort ขึ้นระหว่างปี 1959–60 ตอนเป็นนักศึกษาอยู่ที่มอสโก ทำงานด้านการแปลภาษารัสเซียด้วยเครื่อง และตีพิมพ์มันในปี 1962 (The Computer Journal 5, no. 1: 10–16) กรณีแย่สุด (worst case) ของมันเป็นแบบยกกำลังสอง (quadratic) และฝ่ายตรงข้าม (adversary) ที่รู้กฎของคุณบังคับให้เกิดกรณีนั้นได้ทุกครั้ง เลือกจุดหมุน (pivot) แบบสุ่ม ฝ่ายตรงข้ามคนนั้นก็หมดอาวุธ เพราะเขาต้องเดาลูกเต๋าของคุณให้ถูกเสียก่อน
A data structure is a payment plan. This is the idea that makes the second half of the field cohere. An unsorted array is cheap to add to and expensive to search: you pay at query time, every time. Sorting it is prepayment — one large charge now in exchange for logarithmic lookups forever after. A hash table pays at insertion for near-instant equality lookups but cannot answer "what comes next"; a balanced tree charges a little more per operation and answers ordered questions the hash table cannot. Databases call the same decision an index, and the trade is identical: writes get slower so that reads get faster (chapter 08). Nothing here is free; you are choosing only the currency. And the currency need not be time at all — precompute a lookup table and you have bought speed with memory, which is the space–time trade in its purest form.
โครงสร้างข้อมูล (data structure) คือแผนการผ่อนจ่าย ไอเดียนี้เองที่ทำให้ครึ่งหลังของสาขานี้เชื่อมกันเป็นเนื้อเดียว อาร์เรย์ที่ยังไม่เรียงลำดับเติมข้อมูลเข้าไปได้ถูก แต่ค้นหา (search) แพง คุณจ่ายตอนคิวรี (query) ทุกครั้งไป เรียงลำดับ (sorting) มันเสียก่อนคือการจ่ายล่วงหน้า ก้อนใหญ่ครั้งเดียวตอนนี้ แลกกับการค้นหาแบบลอการิทึมไปตลอด hash table จ่ายตอนใส่ข้อมูล ได้การค้นหาความเท่ากันที่เร็วเกือบทันทีกลับมา แต่ตอบคำถามว่า "ตัวถัดไปคืออะไร" ไม่ได้ ต้นไม้สมดุล (balanced tree) คิดราคาต่อการกระทำแพงกว่านิดหน่อย แต่ตอบคำถามเชิงลำดับที่ hash table ตอบไม่ได้ ฐานข้อมูลเรียกการตัดสินใจอันเดียวกันนี้ว่าดัชนี (index) และการแลกได้แลกเสียก็เหมือนกันเป๊ะ เขียนช้าลงเพื่อให้อ่านเร็วขึ้น (บทที่ 08) ไม่มีอะไรในนี้ฟรี คุณเลือกได้แค่สกุลเงินที่จะจ่าย และสกุลเงินนั้นไม่จำเป็นต้องเป็นเวลาด้วยซ้ำ คำนวณตารางค้นหาไว้ล่วงหน้า คุณก็ซื้อความเร็วมาด้วยหน่วยความจำ นี่คือการแลกกันระหว่างพื้นที่กับเวลาในรูปที่บริสุทธิ์ที่สุด
Some costs are floors, not failures of imagination. Any algorithm that sorts by comparing elements is, in effect, a decision tree: each comparison branches two ways, and the tree must have a distinct leaf for every one of the n! possible orderings. A binary tree with n! leaves has depth at least log₂(n!), which grows like n log n. So no comparison sort can beat Ω(n log n) — not one that is cleverer, only one that stops comparing. Counting sort escapes precisely because it looks at the values themselves rather than at pairwise comparisons. Notice that this is chapter 01's move — counting what a procedure can possibly distinguish — aimed at cost rather than at possibility.
ต้นทุนบางอย่างคือขอบล่าง (lower bound) ไม่ใช่ความล้มเหลวทางจินตนาการ อัลกอริทึมที่เรียงลำดับด้วยการเปรียบเทียบสมาชิก (comparison sort) โดยเนื้อแท้คือต้นไม้การตัดสินใจ (decision tree) การเปรียบเทียบแต่ละครั้งแตกออกสองทาง และต้นไม้ต้องมีใบที่ต่างกันครบทุกหนึ่งในลำดับที่เป็นไปได้ n! แบบ ต้นไม้แบบไบนารี (binary tree) ที่มี n! ใบ ลึกอย่างน้อย log₂(n!) ซึ่งโตแบบ n log n ฉะนั้นไม่มี comparison sort ตัวไหนเอาชนะ Ω(n log n) ได้ ตัวที่ฉลาดกว่าก็ไม่ช่วย มีแต่ตัวที่เลิกเปรียบเทียบเท่านั้นที่ทำได้ counting sort หลุดออกไปได้เพราะมันมองที่ค่าจริงๆ แทนการเปรียบเทียบเป็นคู่ๆ สังเกตว่านี่คือท่าเดียวกับบทที่ 01 — นับว่ากระบวนการหนึ่งแยกแยะอะไรได้บ้าง — เพียงแต่เล็งไปที่ต้นทุนแทนความเป็นไปได้
And the model leaks. Big-O hides constants, and sometimes the constants are the whole story: Lipton and Regan named the class of galactic algorithms — asymptotically superior, never used, because the input size at which they win exceeds anything that exists (2010). Big-O also hides the machine. Two loops with identical asymptotic cost can differ tenfold because one walks memory in order and the other jumps, which is chapter 04's floor leaking upward. And worst case is not typical case, as chapter 01's SAT solvers demonstrate daily. Asymptotic cost is the price on the label; what you pay at the till still depends on the machine.
แบบจำลองนี้รั่ว (leak) ด้วย Big-O ซ่อนค่าคงที่ไว้ และบางครั้งค่าคงที่นั่นแหละคือเรื่องทั้งหมด Lipton และ Regan ตั้งชื่อกลุ่มนี้ว่า อัลกอริทึมกาแล็กติก (galactic algorithms) คือพวกที่เหนือกว่าในเชิงเส้นกำกับ (asymptotic) แต่ไม่เคยถูกใช้จริง เพราะขนาดอินพุตที่มันเริ่มชนะนั้นใหญ่เกินกว่าอะไรที่มีอยู่จริง (2010) Big-O ซ่อนตัวเครื่องไว้อีกชั้น ลูปสองลูปที่มีต้นทุนแบบ asymptotic เท่ากันเป๊ะ ต่างกันสิบเท่าได้ เพราะลูปหนึ่งเดินหน่วยความจำเรียงตามลำดับ อีกลูปกระโดดไปมา นั่นคือชั้นของบทที่ 04 รั่วขึ้นมา และกรณีแย่สุดก็ไม่ใช่กรณีทั่วไป อย่างที่ตัวแก้ปัญหา SAT (SAT solvers) ในบทที่ 01 แสดงให้เห็นทุกวัน ต้นทุนแบบ asymptotic คือราคาบนป้าย สิ่งที่คุณจ่ายจริงตอนหน้าเคาน์เตอร์ยังขึ้นกับตัวเครื่องอยู่ดี
Connections
เชื่อมโยง
Below: 01, which decides what is possible before this floor asks what it costs. Beside it: 03, which supplies the counting that turns log₂(n!) into a genuine information-theoretic bound. Above: 04, where the memory hierarchy decides which constant factors are real; 08, where B-trees are a data structure shaped by the cost of touching a disk; 12, where the training of a model is dominated by exactly the matrix multiplication Strassen attacked.
ชั้นล่าง: บทที่ 01 ตัดสินว่าอะไรเป็นไปได้ ก่อนที่ชั้นนี้จะถามว่ามันมีต้นทุนเท่าไร ชั้นข้างเคียง: บทที่ 03 ให้การนับที่เปลี่ยน log₂(n!) ให้เป็นขอบเขตเชิงทฤษฎีสารสนเทศ (information-theoretic bound) ตัวจริง ชั้นบน: บทที่ 04 ที่ลำดับชั้นหน่วยความจำ (memory hierarchy) ตัดสินว่าค่าคงที่ตัวไหนมีผลจริง บทที่ 08 ที่ B-tree เป็นโครงสร้างข้อมูลที่ถูกปั้นขึ้นด้วยต้นทุนของการแตะดิสก์ บทที่ 12 ที่การเทรนโมเดลถูกครอบงำโดยการคูณเมทริกซ์ตัวเดียวกับที่ Strassen เข้าโจมตี
Open questions
คำถามที่ยังเปิดอยู่
Is the true exponent of matrix multiplication 2? Sixty years of work has moved it from 3 to about 2.371 and stalled far above the obvious lower bound. More broadly: is worst-case analysis still the right instrument, when the algorithms that matter commercially are judged on inputs that are anything but adversarial? And is the catalogue of strategies above complete — or is there a fifth idea, as basic as divide-and-conquer, that nobody has had yet?
เลขชี้กำลังที่แท้จริงของการคูณเมทริกซ์คือ 2 หรือไม่ หกสิบปีของความพยายามเลื่อนมันจาก 3 มาอยู่ราว 2.371 แล้วค้างอยู่ห่างจากขอบล่างที่ชัดเจนอยู่มาก มองกว้างกว่านั้น — การวิเคราะห์กรณีแย่สุด (worst-case analysis) ยังเป็นเครื่องมือที่ถูกต้องอยู่หรือไม่ ในเมื่ออัลกอริทึมที่สำคัญเชิงพาณิชย์ถูกตัดสินบนอินพุตที่ไม่ได้เป็นปฏิปักษ์เลยสักนิด และรายการกลยุทธ์ข้างต้นครบแล้วหรือยัง หรือยังมีไอเดียที่ห้า พื้นฐานพอๆ กับ divide-and-conquer ที่ยังไม่มีใครคิดถึงมัน
Go deeper
อ่านต่อ
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — the reference; §8.1 has the sorting lower bound in full (MIT Press).
- Edsger Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1 (1959): 269–271 — three pages, two algorithms, no wasted sentence (PDF).
- Volker Strassen, "Gaussian elimination is not optimal," Numerische Mathematik 13 (1969): 354–356 — three pages that started a fifty-year race (Springer).
- Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — เล่มอ้างอิงหลัก §8.1 มีขอบล่างของการเรียงลำดับแบบเต็มรูปแบบ (MIT Press).
- Edsger Dijkstra, "A Note on Two Problems in Connexion with Graphs," Numerische Mathematik 1 (1959): 269–271 — สามหน้า สองอัลกอริทึม ไม่มีประโยคไหนฟุ่มเฟือย (PDF).
- Volker Strassen, "Gaussian elimination is not optimal," Numerische Mathematik 13 (1969): 354–356 — สามหน้าที่จุดชนวนการแข่งขันที่ยาวนานห้าสิบปี (Springer).