algorithm - 如何为 Graham Scan 生成最坏情况数据

Question

我知道格雷厄姆扫描的最坏情况运行时间是 O(nlogn) 但我不确定如何生成最坏情况数据。据我了解，这发生在对点进行排序的步骤中，这是否意味着我应该为我使用的排序算法生成最坏的情况数据？

任何帮助，将不胜感激。

Answer 1

是的，正如马特所指出的，您需要为排序算法生成最坏情况，因为算法的其余部分在最坏情况线性时间内运行。这种排序算法应该是比较排序；否则，下限可能无效。

不幸的是，在不知道排序算法的情况下，很难指出触发最坏情况的特定输入。某些排序，例如快速排序和归并排序，是最佳情况 Θ(n log n)。其他的，比如 Timsort 和 smoothsort，有线性时间最好的情况。不幸的是，给定任何需要长度（一元）并返回排列的线性时间过程，有一个排序算法通过检查输入是否以这种方式排列，然后返回到合并排序，在这些特定排列上以线性时间运行必要的。

对于未指定的算法，我能做的最好的事情是建议你选择一个统一的随机排列，因为每个正确的比较排序在这个输入分布上平均 Ω(n log n) 时间。