知识卡片
格雷厄姆扫描包含排序成本
格雷厄姆扫描先按适当的极角等顺序排列输入点,再以栈维护候选边界,遇到不符合凸性方向时弹出。每点最多入栈和出栈一次,扫描阶段O(n),通常排序O(n log n),整体O(n log n)。
这里n是输入点数,而非原文所写的凸包输出点数;输出点数h可远小于n。共线、重复点和角度相同的排序规则会影响边界结果,需要具体实现定义。书中只给算法概览,没有提供代码。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
格雷厄姆扫描 这是一种计算凸包的方法,可以作为Jarvis's march的替代方法。格雷厄姆扫描维护一个凸包候选点的栈结构。每个点只压入栈一次。所有不属于凸包内的点最终都会弹出栈,这样当该算法结束时,栈就只包含属于凸包内的点。格雷厄姆扫描法的时间复杂度为O(n lg n),这里的n代表凸包包含的点
参考来源
- 位置:《算法精解:C语言描述》第17章《相关主题》(spine1436;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1402.html;u325-ch17-017)。
- 结论依据:325全文格雷厄姆扫描相关段实读,输入规模和排序成本按算法机制解释。
- 原始内容:格雷厄姆扫描 这是一种计算凸包的方法,可以作为Jarvis's march的替代方法。格雷厄姆扫描维护一个凸包候选点的栈结构。每个点只压入栈一次。所有不属于凸包内的点最终都会弹出栈,这样当该算法结束时,栈就只包含属于凸包内的点。格雷厄姆扫描法的时间复杂度为O(n lg n),这里的n代表凸包包含的点