算法设计与分析基础报告
2010/10/8
算法分析与设计基础报告
- 1 -
1 最近点对问题 ......................................................................................................................... - 2 -
1.1 算法 ................................................................................................................................. - 2 -
1.1.1 算法 .............................................................................................................. - 2 -
1.1.2 算法 ........................................................................................................ - 2 -
1.1.3 算法剪枝 ...................................................................................................... - 2 -
1.2 手动选点 ......................................................................................................................... - 2 -
1.2.1 概述 ......................................................................................................................... - 2 -
1.2.2 数据结构 ................................................................................................................. - 3 -
1.2.3 性能比较 ................................................................................................................. - 3 -
1.3 随机生成点 ..................................................................................................................... - 3 -
1.3.1 概述 ......................................................................................................................... - 3 -
1.3.2 数据结构 ................................................................................................................. - 3 -
1.3.3 性能比较 ................................................................................................................. - 3 -
2 Fibonacci 数 ............................................................................................................................. - 5 -
2.1 通项公式法 ..................................................................................................................... - 5 -
2.2 递推法 ............................................................................................................................. - 5 -
2.3 递归法 ............................................................................................................................. - 6 -
2.4 矩阵法 ............................................................................................................................. - 6 -
2.5 算法的评估 ..................................................................................................................... - 6 -
3 Armstrong 的错误 ................................................................................................................... - 7 -
4 PERMUTE-BY-SORTING ............................................................................................................ - 7 -
算法分析与设计基础报告
- 2 -
1 最近点对问题
1.1 算法
1.1.1
算法
枚举所有点对
, 共有
种可能性, 如果
则
置
.
1.1.2 算法
设为平面上点的序列(根据横坐标排序). 为点序列中的最
近点对的距离. 于是
其中
为的左半子点序列,
为的右半子点序列.
为
划分横坐标两侧
长度范围内的点序列.
1.1.3
算法剪枝
分析以上两个算法, 时间复杂度相差比较大的原因是,
的
算法比较次数太多, 很多点对之间距离相差甚远, 却仍然进行了距离
的计算. 针对这个弊端. 考虑对
算法进行优化, 设法减少点对
距离的计算次数.
如果将点集按横坐标升序排列, 那么横坐标差较大的点的距离
也很可能较大. 所以尽量避免那样的运算. 所以, 最起码说, 如果横
坐标差已经大于当前的最小值, 则后继的循环则是没有必要的了.
整理一下, 算法过程如下:
将点集按 x 坐标排序, 得到 x 坐标有序点列 A
令
从前到后枚举所有点, 当前为
从该点的后一个点开始枚举所有点, 当前为
如果
, 则结束当前内循环
否则若
, 则
在平面点分布情况比较随机的条件下, 较早比较的点距离较近,
得到的较小, 于是便可以忽略较多的靠后面的点, 所以算法收敛
速度非常大. 这一特点在大量随机点的情况下尤为突出.
1.2 手动选点
1.2.1 概述
通过用户在窗口中指定区域点击鼠标左键获取点. 由于屏幕的
像素限制, 点数不一定能达到较大的规模, 而且只能选定该范围内的
整数点, 所以仅适用于要求整点, 点数较少, 要求结果直观的情况.
配套程序中实现了鼠标取点, 和清空点的操作. 提供了
,
