algorithm - 用于螺母和 bolt 匹配的最坏情况 NlogN 算法

Question

Find the unique mapping between elements of two same size arrays

这是一个众所周知的面试问题，很容易找到平均情况复杂度为 O(NlogN) 和最坏情况复杂度为 O(N^2) 的算法(使用快速排序的思想)。同样使用与排序问题相同的技术，我们可以证明任何算法都应该至少进行 NlogN 次比较。

所以我无法回答的问题是，这个问题是否有最坏情况 O(NlogN) 算法？也许应该类似于归并排序。

Answer 1

是的，截至 1995 年，已知有最坏情况下的 O(n log n) 时间算法可以解决此问题，但它们看起来相当复杂。这是来自 Jeff Erickson's algorithm notes 的两个引用:

1. János Komlós、Yuan Ma 和 Endre Szemerédi，在 O(n log n) 时间内对螺母和 bolt 进行排序，SIAM J. Discrete Math 11(3):347–372, 1998。

2. Phillip G. Bradford，Matching nuts and bolts optimally，技术报告 MPI-I-95-1-025，Max-Planck-Institut für Informatik，1995 年 9 月。

正如 Jeff 所说，“算法及其分析都非常技术性，隐藏在 O(·) 表示法中的常量非常大。”他还指出，出现在第二位的 Bradford 算法稍微更简单。