适用于期末考试总复习，内涵多个试题及答案
对于下列各组函数f(n)和g(n)，确定f(n)=O(g(n))或 或 ，并简述理由。
2023-11-01 21:12:29
105KB
1
这是一本具有启发性的很好的书，翻译的也还不错。
我们的实际生活中有很多的问题亟待解决，当问题很复杂的时候往往让人无从下手，这时候如果利用数学中的几何知识将之转化成为几何问题求解往往会出现出人意料的解决方案。
书中关于点的处理的部分有凸包、正交区域查找、点定位、voronoi图和delaunay三角剖分。
1、凸包：
1）平面凸包：计算平面上由n个点组成的有限集合P的凸包，利用“递增式算法”，逐一引入P中的各点，每增加一个点，观察多边形的外边界是向哪个方向改变，例如：对于点集的上凸包，当其多边形外边界向左转构成一个左拐时就删除当前引入的点。（这部分内容比较有用，待用到的时候再好好研究一下）
2）三维凸包：
选出三维点集中不共面的4个点，构成一个凸包四面体，然后将剩余的点随即加入，动态维护凸包。采用双向链接边表存储凸包。
2、正交区域查找
1）一维区域查找：采用平衡二分查找树从根节点开始，每向左前进一步，枚举出该处右子树中的所有叶子，同时每向右前进一步，枚举右该处左子树中的所有叶子，遍历整棵子树后，报告出所有叶子对应的点。
2）二维区域查找：
采用KD－树：先将点集沿x坐标方向划分，再沿y方向划分，再x方向，再y方向……直到达到给定的递归深度。
采用区域树：利用一维区域查找，先找出x坐标方向的区域内的所有点，对这些点再作y方向的一维区域查找。
3、点定位：
方法一：将包含n条线段的平面子区域划分为竖条带，先用二分查找找出待查点q所处的竖条带，然后在该竖条带所对应的数组重，再次进行二分查找，找出q下方紧挨着的那条线段。
方法二：梯形图，经过线段集中每条线段的每个端点，向上向下各作一条垂线构成梯形图。
4、voronoi图和delaunay三角剖分
二者互为对偶
文中提到构造delaunay三角剖分的准则来历。
书中提到的对偶概念也很有趣，尤其是抛物线的对偶有一些非常神奇的性质，因为和点无关，就在这里不提了
2023-03-17 21:54:14
7.5MB
1
汇总了计算机研究生复试有关算法分析与设计各章节简答题，使用了易于口头表达的语言进行了总结。包括算法分析与设计基本概念及各章节问题回答。可供研究生复试或相关专业岗位面试使用。
1. 简述算法定义、属性及指标；
2. 什么是算法分析，怎么做算法设计；
3. 什么是算法复杂性；
4. 枚举法算法的基本思想；
5. 枚举法算法解决的典型问题有哪些，举例说明算法处理过程？
6. 分治法算法的基本思想；
7. 分治法算法解决的典型问题有哪些，举例说明算法处理过程？
8. 动态规划算法的基本思想；
9. 动态规划算法解决的典型问题有哪些，举例说明算法处理过程？
10. 贪心算法的基本思想；
12. 分治法、贪心算法与动态规划算法的差异；
13. 回溯法的基本思想；
15. 分支限界法的基本思想；
17. 简述分支限界法与回溯法的不同点；
18. 基于分治法的排序算法有哪些？
2023-03-08 09:26:31
266KB
1