知识卡片

普通读书笔记卡 · 8093.p · 生成模型:未记录

格雷厄姆扫描包含排序成本

理解等级:中级

格雷厄姆扫描先按适当的极角等顺序排列输入点,再以栈维护候选边界,遇到不符合凸性方向时弹出。每点最多入栈和出栈一次,扫描阶段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代表凸包包含的点