最壞情況NlogN算法螺母和螺栓匹配

這是相當知名的面試問題，很容易（使用快速排序的想法），其具有平均情況和O O（NlogN）來查找算法（N^2）最壞情況的複雜性。同樣使用與排序問題相同的技術，我們可以證明任何算法都應至少進行NlogN比較。

因此，我不能得到答案的問題，是否存在這種問題的最壞情況O（NlogN）算法？也許它應該類似於合併排序。

2014-12-31 Ashot

是的，如果您的瓶頸正在排序，您可以使用合併排序或堆排序或其他變體來獲取O（nlogn）最壞的情況。 – amit

我知道最壞的情況O（nlogn）算法存在排序，但無法弄清楚如何使用它們來解決這個問題。 – Ashot

@amit您沒有閱讀實際問題。合併排序取決於比較元素與對方。這個問題涉及到排序兩個數組，每個數組的成員只能彼此進行比較。 – btilly

是的，到1995年爲止，已經存在最壞的O（n log n）時間算法，但它們看起來相當複雜。下面是從Jeff Erickson's algorithm notes 2個引文：

由於傑夫評論說：「算法和他們的分析都非常技術化，並且不斷被隱藏起來O（·）符號中的書庫非常大。「他還指出，布拉德福德的算法，其次是，稍微簡單。

2014-12-31 14:25:21

回答