SMAWK Algorithm

定义 Definition

SMAWK 算法是一种用于在全单调矩阵（totally monotone matrix）中高效寻找每一行最小值所在列的算法，时间复杂度可达 O(m+n)（对一个 m×n 矩阵）。它常用于Monge 数组/矩阵相关问题，以及一些动态规划的优化中。

发音 Pronunciation (IPA)

/ˈsmɔːk ˈælɡəˌrɪðəm/

例句 Examples

The SMAWK algorithm finds the minimum element in each row of a totally monotone matrix efficiently.
SMAWK 算法可以高效地在全单调矩阵中找出每一行的最小元素位置。

By exploiting the Monge property, we can apply the SMAWK algorithm to speed up the dynamic programming transition from quadratic time to near-linear time.
利用 Monge 性质，我们可以用 SMAWK 算法把动态规划的转移从平方时间加速到接近线性时间。

词源 Etymology

“SMAWK”来自提出该算法的五位作者姓氏首字母缩写：Shor、Moran、Aggarwal、Wilber、Klawe。它最早与“矩阵搜索（matrix searching）”问题相关，并在计算几何与算法理论中得到广泛引用。

相关词 Related Words

• Monge Array
• Totally Monotone Matrix
• Matrix Searching
• Dynamic Programming
• Divide And Conquer
• Convex Hull Trick

文学与著作 Literary Works

• Aggarwal, Klawe, Moran, Shor, Wilber：《Geometric Applications of a Matrix-Searching Algorithm》（提出并系统讨论该类矩阵搜索算法，SMAWK 因此得名并被广泛传播）
• 相关算法教材/讲义：计算几何与高级算法课程资料中常在“Monge 阵/全单调矩阵”“矩阵最小值搜索”章节引用 SMAWK 算法（作为经典线性时间矩阵搜索工具）