螺母和螺栓匹配的最坏情况 NlogN 算法 [英] Worst case NlogN algorithm for Nuts and bolts matching
问题描述
这是一个众所周知的面试问题，很容易找到算法(使用快速排序的思想)，平均情况为 O(NlogN)，最坏情况的复杂性为 O(N^2).同样使用与排序问题相同的技术，我们可以证明任何算法都应该至少进行 NlogN 次比较.
This is quite known interview question and it is easy to find algorithm (using the idea of quicksort) that has O(NlogN) for average case and O(N^2) for worst case complexity. Also using the same techniques as for sorting problem we can show that any algorithm should do at least NlogN comparisons.
所以我无法回答的问题，这个问题有最坏情况的 O(NlogN) 算法吗?也许应该类似于归并排序.
So the question I cant get answered, is there worst case O(NlogN) algorithm for this problem? Maybe it should be similar to merge sort.
推荐答案
是的，截至 1995 年，有已知的最坏情况 O(n log n) 时间算法解决此问题，但它们似乎相当复杂.以下是 Jeff Erickson 的算法笔记:
Yes, as of 1995 there are worst-case O(n log n)-time algorithms known for this problem, but they appear to be quite complicated. Here are two citations from Jeff Erickson's algorithm notes:
János Komlós、Yuan Ma 和 Endre Szemerédi，在 O(n log n) 时间内对螺母和螺栓进行排序，SIAM J. Discrete Math 11(3):347–372, 1998.
János Komlós, Yuan Ma, and Endre Szemerédi, Sorting nuts and bolts in O(n log n) time, SIAM J. Discrete Math 11(3):347–372, 1998.
Phillip G. Bradford，最佳匹配螺母和螺栓，技术报告 MPI-I-95-1-025，Max-Planck-Institut für Informatik，1995 年 9 月.
Phillip G. Bradford, Matching nuts and bolts optimally, Technical Report MPI-I-95-1-025, Max-Planck-Institut für Informatik, September 1995.
正如 Jeff 所说，算法及其分析都非常技术性，隐藏在 O(·) 符号中的常数非常大."他还指出，排在第二位的 Bradford 算法稍微简单.
As Jeff remarks, "Both the algorithms and their analysis are incredibly technical and the constant hidden in the O(·) notation is quite large." He notes also that Bradford’s algorithm, which appeared second, is slightly simpler.
这篇关于螺母和螺栓匹配的最坏情况 NlogN 算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
