| 实验报告 |
|---|
| 课程名称 |
| 学生姓名 |
| 实验名称 |
| 实验地点 |
| 1. |
| 给定平面上的n个点 求其中最近的点对 |
| 2. |
| 这是一个经典的问题，可以采用分治策略解决。 |
| 将平面按照x轴划分为左右两个区域，现对横跨左右的点对进行统计，容易发现每次只要对结果取min即可 |
| 类似于二分法的性质，容易得到会进行logN次划分，每次划分只需要用类似双指针的思想线性扫描即可归并 |
| 3. |
| SORT_X(P.Begin,P,end) |
| RUN(BEGIN,END) |
| FUNCTION RUN(L,R) |
| 4. |
| 容易发现最多进行logN次划分（也就是这里的分治） |
| 每次划分用类似双指针的思想即可On扫描 |
| 因此Tn = 2T(n / 2) + n |
| 复杂度O(n) = NlogN |
| 5. |
| Algorithm-Class-codes/project5 at main · MQFLLY/Algorithm-Class-codes (github.com) |
相关文章
- 02-08案例分析：设计模式与代码的结构特性
- 02-08斗地主算法的设计与实现--项目介绍&如何定义和构造一张牌
- 02-08C程序设计的抽象思维-算法分析-大多数元素
- 02-08RBAC权限系统分析、设计与实现
- 02-08RBAC权限系统分析、设计与实现
- 02-08数据结构与算法分析笔记-前置知识
- 02-08数字信号处理设计与仿真分析
- 02-08算法分析与设计实践作业8
- 02-08ADS实验报告三：匹配电路的设计与仿真
- 02-08算法设计与分析（三）分治法--快速排序的递归和非递归实现