给定平面上 n 个不同的点,如何快速找出包含所有点的最小凸多边形(凸包)?以下哪种方法在最坏情况下具有最优的时间复杂度?

答案解析

选项 A 的时间复杂度为 O(n^3),效率极低。选项 B 中的 Graham 扫描法,先排序,再扫描,时间复杂度为 O(n log n) + O(n) = O(n log n),是常见的最优凸包算法之一。选项 C 的极角排序虽然可以通过atan2函数进行,但排序的时间复杂度为 O(n log n),且随机选取的点可能不位于凸包上,需要后续处理. 选项D与C相似,区别在于起始点的选取方式不同,但整体时间复杂度依然是 O(n log n). Graham 扫描法通过排序和栈操作,能保证最坏情况下O(n log n)的时间复杂度.
正确答案:B
随机推荐
开始刷题