02 · อัลกอริทึมและโครงสร้างข้อมูล
ชั้นนี้วางอยู่เหนือเรื่องคำนวณได้ (computability) ขึ้นมาหนึ่งชั้นพอดี — บทที่ 01 บอกว่างานหนึ่งทำได้หรือไม่ ชั้นนี้ถามว่าทำแล้วเสียต้นทุนเท่าไร
ในเมื่อคำนวณได้แล้ว จะทำได้ดีแค่ไหน
ปี 1960 ในสัมมนาที่เขาเป็นผู้นำที่มหาวิทยาลัยมอสโก Andrey Kolmogorov บอกกับคนทั้งห้องว่า การคูณเลข n หลักสองจำนวนต้องเสียต้นทุนราว n² ครั้งของการกระทำพื้นฐาน วิธีที่เด็กนักเรียนทุกคนเรียนกัน คูณหลักต่อหลัก คือวิธีที่ดีที่สุดเท่าที่จะมีได้ ความเชื่อนี้มีเหตุผลรองรับ อัลกอริทึม (algorithm) การคูณทุกตัวที่เคยมีคนเขียนขึ้นมาล้วนทำงานแบบนั้น และข้อคาดการณ์ของ Kolmogorov ก็ไม่ใช่ของที่ผิดกันง่ายๆ
นักศึกษาในห้องคนหนึ่งชื่อ Anatoly Karatsuba หักล้างมันได้ภายในสัปดาห์เดียว กลเม็ดของเขาเล็กจนน่าอาย คือตัดเลขแต่ละจำนวนออกเป็นครึ่ง วิธีแบบตำราต้องใช้ผลคูณขนาดครึ่งถึงสี่ตัว Karatsuba เห็นว่าสามตัวก็พอ เพราะตัวที่สี่หาได้จากการลบตัวที่มีอยู่แล้วออกจากกัน ทำแบบนี้ซ้ำลงไปเรื่อยๆ (recursion) ต้นทุนลดจาก n² เหลือ n^log₂3 หรือราว n^1.585 การประชุมครั้งถัดมา Kolmogorov รายงานข้อหักล้างนั้นด้วยตัวเอง แล้วปิดสัมมนาไปเลย (Karatsuba, The Complexity of Computations, 1995)
โลกไม่ได้เปลี่ยนไปเลยในสัปดาห์นั้น ไม่มีเครื่องใหม่ ไม่มีฟิสิกส์ใหม่ สิ่งที่ถูกค้นพบคือข้อเท็จจริงเกี่ยวกับ ต้นทุน ค้นพบในแบบเดียวกับที่คนค้นพบข้อเท็จจริงเกี่ยวกับธรรมชาติ — และนี่คือสิ่งที่ชั้นนี้ศึกษา
ต้นทุนเป็นรูปทรง ไม่ใช่ตัวเลข สัญกรณ์ที่ใช้แทนมันยืมมาจากทฤษฎีจำนวน Paul Bachmann เสนอ Big-O ครั้งแรกในปี 1894 Edmund Landau รับมาใช้ต่อในปี 1909 พร้อมให้เครดิตเขา (MAA Convergence) บันทึกของ Donald Knuth ในปี 1976 ใน SIGACT News ผลักให้วงการคอมพิวเตอร์ยึด O, Ω และ Θ เป็นมาตรฐานเดียวกัน (Knuth, 1976) สังเกตสิ่งที่สัญกรณ์นี้ตั้งใจโยนทิ้ง คือค่าคงที่ นั่นไม่ใช่ความมักง่าย ค่าคงที่คือส่วนของต้นทุนที่ฮาร์ดแวร์ คอมไพเลอร์ และการเขียนโค้ดอย่างระมัดระวังยังขยับได้ ส่วน อัตรา การเติบโตเป็นของอัลกอริทึมเอง วิศวกรรมชั้นล่างเท่าไรก็เปลี่ยนมันไม่ได้ เครื่องที่เร็วขึ้นสิบเท่าซื้อค่าคงที่ให้คุณ เลขชี้กำลังซื้ออนาคตให้คุณ เฉพาะเลขชี้กำลังของ Karatsuba อย่างเดียวก็ประหยัดได้ราวสิบแปดเท่าที่พันหลัก และสามร้อยเท่าที่ล้านหลัก
กลยุทธ์ไม่กี่ข้อครอบคลุมสนามนี้ไว้เกือบทั้งหมด คุ้มที่จะจำไว้ทีละชื่อ เพราะแทบทุกอัลกอริทึมที่คุณจะเจอ คือหนึ่งในนี้ที่สวมเสื้อผ้าเฉพาะถิ่นเข้ามา
แบ่งแล้วพิชิต (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) และไม่มีใครรู้ว่ามันลงไปได้ลึกแค่ไหน
กลยุทธ์ greedy คว้าก้าวที่ดีที่สุดตรงหน้าแล้วไม่หันกลับไปมองอีก จะไร้เดียงสาหรือเหมาะที่สุด ขึ้นอยู่กับว่าโจทย์มีโครงสร้างที่ตอบแทนวิธีนี้หรือไม่ล้วนๆ และเมื่อโจทย์มี greedy ก็เอาชนะไม่ได้เลย อัลกอริทึมหาเส้นทางสั้นสุดของ Dijkstra คือตัวอย่างคลาสสิก ตีพิมพ์ในสามหน้าเมื่อปี 1959 (Numerische Mathematik 1: 269–271) ตามคำบอกเล่าของเขาเอง เขาคิดมันขึ้นมาในราวยี่สิบนาทีเมื่อปี 1956 ไม่มีดินสอ ไม่มีกระดาษ นั่งอยู่ที่ระเบียงคาเฟ่ในอัมสเตอร์ดัมระหว่างออกไปช็อปปิ้งกับคู่หมั้น (oral history, Charles Babbage Institute, 2001)
เมื่อโจทย์ย่อยเกิดซ้ำ 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) ตัวเทคนิคซื่อตรงกว่าชื่อของมัน มันคือการแลกหน่วยความจำเอาเวลากลับมา เท่านั้นเอง
แปลกที่สุดในสี่กลยุทธ์นี้คือ การสุ่ม (randomization) ที่ชนะด้วยการไม่ยอมให้ใครทายทางถูก Tony Hoare คิด Quicksort ขึ้นระหว่างปี 1959–60 ตอนเป็นนักศึกษาอยู่ที่มอสโก ทำงานด้านการแปลภาษารัสเซียด้วยเครื่อง และตีพิมพ์มันในปี 1962 (The Computer Journal 5, no. 1: 10–16) กรณีแย่สุด (worst case) ของมันเป็นแบบยกกำลังสอง (quadratic) และฝ่ายตรงข้าม (adversary) ที่รู้กฎของคุณบังคับให้เกิดกรณีนั้นได้ทุกครั้ง เลือกจุดหมุน (pivot) แบบสุ่ม ฝ่ายตรงข้ามคนนั้นก็หมดอาวุธ เพราะเขาต้องเดาลูกเต๋าของคุณให้ถูกเสียก่อน
โครงสร้างข้อมูล (data structure) คือแผนการผ่อนจ่าย ไอเดียนี้เองที่ทำให้ครึ่งหลังของสาขานี้เชื่อมกันเป็นเนื้อเดียว อาร์เรย์ที่ยังไม่เรียงลำดับเติมข้อมูลเข้าไปได้ถูก แต่ค้นหา (search) แพง คุณจ่ายตอนคิวรี (query) ทุกครั้งไป เรียงลำดับ (sorting) มันเสียก่อนคือการจ่ายล่วงหน้า ก้อนใหญ่ครั้งเดียวตอนนี้ แลกกับการค้นหาแบบลอการิทึมไปตลอด hash table จ่ายตอนใส่ข้อมูล ได้การค้นหาความเท่ากันที่เร็วเกือบทันทีกลับมา แต่ตอบคำถามว่า "ตัวถัดไปคืออะไร" ไม่ได้ ต้นไม้สมดุล (balanced tree) คิดราคาต่อการกระทำแพงกว่านิดหน่อย แต่ตอบคำถามเชิงลำดับที่ hash table ตอบไม่ได้ ฐานข้อมูลเรียกการตัดสินใจอันเดียวกันนี้ว่าดัชนี (index) และการแลกได้แลกเสียก็เหมือนกันเป๊ะ เขียนช้าลงเพื่อให้อ่านเร็วขึ้น (บทที่ 08) ไม่มีอะไรในนี้ฟรี คุณเลือกได้แค่สกุลเงินที่จะจ่าย และสกุลเงินนั้นไม่จำเป็นต้องเป็นเวลาด้วยซ้ำ คำนวณตารางค้นหาไว้ล่วงหน้า คุณก็ซื้อความเร็วมาด้วยหน่วยความจำ นี่คือการแลกกันระหว่างพื้นที่กับเวลาในรูปที่บริสุทธิ์ที่สุด
ต้นทุนบางอย่างคือขอบล่าง (lower bound) ไม่ใช่ความล้มเหลวทางจินตนาการ อัลกอริทึมที่เรียงลำดับด้วยการเปรียบเทียบสมาชิก (comparison sort) โดยเนื้อแท้คือต้นไม้การตัดสินใจ (decision tree) การเปรียบเทียบแต่ละครั้งแตกออกสองทาง และต้นไม้ต้องมีใบที่ต่างกันครบทุกหนึ่งในลำดับที่เป็นไปได้ n! แบบ ต้นไม้แบบไบนารี (binary tree) ที่มี n! ใบ ลึกอย่างน้อย log₂(n!) ซึ่งโตแบบ n log n ฉะนั้นไม่มี comparison sort ตัวไหนเอาชนะ Ω(n log n) ได้ ตัวที่ฉลาดกว่าก็ไม่ช่วย มีแต่ตัวที่เลิกเปรียบเทียบเท่านั้นที่ทำได้ counting sort หลุดออกไปได้เพราะมันมองที่ค่าจริงๆ แทนการเปรียบเทียบเป็นคู่ๆ สังเกตว่านี่คือท่าเดียวกับบทที่ 01 — นับว่ากระบวนการหนึ่งแยกแยะอะไรได้บ้าง — เพียงแต่เล็งไปที่ต้นทุนแทนความเป็นไปได้
แบบจำลองนี้รั่ว (leak) ด้วย Big-O ซ่อนค่าคงที่ไว้ และบางครั้งค่าคงที่นั่นแหละคือเรื่องทั้งหมด Lipton และ Regan ตั้งชื่อกลุ่มนี้ว่า อัลกอริทึมกาแล็กติก (galactic algorithms) คือพวกที่เหนือกว่าในเชิงเส้นกำกับ (asymptotic) แต่ไม่เคยถูกใช้จริง เพราะขนาดอินพุตที่มันเริ่มชนะนั้นใหญ่เกินกว่าอะไรที่มีอยู่จริง (2010) Big-O ซ่อนตัวเครื่องไว้อีกชั้น ลูปสองลูปที่มีต้นทุนแบบ asymptotic เท่ากันเป๊ะ ต่างกันสิบเท่าได้ เพราะลูปหนึ่งเดินหน่วยความจำเรียงตามลำดับ อีกลูปกระโดดไปมา นั่นคือชั้นของบทที่ 04 รั่วขึ้นมา และกรณีแย่สุดก็ไม่ใช่กรณีทั่วไป อย่างที่ตัวแก้ปัญหา SAT (SAT solvers) ในบทที่ 01 แสดงให้เห็นทุกวัน ต้นทุนแบบ asymptotic คือราคาบนป้าย สิ่งที่คุณจ่ายจริงตอนหน้าเคาน์เตอร์ยังขึ้นกับตัวเครื่องอยู่ดี
เชื่อมโยง
ชั้นล่าง: บทที่ 01 ตัดสินว่าอะไรเป็นไปได้ ก่อนที่ชั้นนี้จะถามว่ามันมีต้นทุนเท่าไร ชั้นข้างเคียง: บทที่ 03 ให้การนับที่เปลี่ยน log₂(n!) ให้เป็นขอบเขตเชิงทฤษฎีสารสนเทศ (information-theoretic bound) ตัวจริง ชั้นบน: บทที่ 04 ที่ลำดับชั้นหน่วยความจำ (memory hierarchy) ตัดสินว่าค่าคงที่ตัวไหนมีผลจริง บทที่ 08 ที่ B-tree เป็นโครงสร้างข้อมูลที่ถูกปั้นขึ้นด้วยต้นทุนของการแตะดิสก์ บทที่ 12 ที่การเทรนโมเดลถูกครอบงำโดยการคูณเมทริกซ์ตัวเดียวกับที่ Strassen เข้าโจมตี
คำถามที่ยังเปิดอยู่
เลขชี้กำลังที่แท้จริงของการคูณเมทริกซ์คือ 2 หรือไม่ หกสิบปีของความพยายามเลื่อนมันจาก 3 มาอยู่ราว 2.371 แล้วค้างอยู่ห่างจากขอบล่างที่ชัดเจนอยู่มาก มองกว้างกว่านั้น — การวิเคราะห์กรณีแย่สุด (worst-case analysis) ยังเป็นเครื่องมือที่ถูกต้องอยู่หรือไม่ ในเมื่ออัลกอริทึมที่สำคัญเชิงพาณิชย์ถูกตัดสินบนอินพุตที่ไม่ได้เป็นปฏิปักษ์เลยสักนิด และรายการกลยุทธ์ข้างต้นครบแล้วหรือยัง หรือยังมีไอเดียที่ห้า พื้นฐานพอๆ กับ divide-and-conquer ที่ยังไม่มีใครคิดถึงมัน
อ่านต่อ
- 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).