终其一生,我们只不过在寻找自己

0%

CSIT5500-2 分治

算法理解了就很简单,写代码也容易,但是表达清楚原理就很麻烦。如果没看懂就去看大神的博客吧。

分治法

分治法其实很常见,在并归排序的过程也用上了。
接下来举一个例子:

寻找平面内最近的一对点

https://blog.csdn.net/weixin_37540865/article/details/78201399

  • 暴力:计算n个点两两距离,O(N^2)
  • 分治:
    • 对于所有有点,按照一个轴排序O(nlog(n)),一分为二
    • 找到左右各自最短距离dl, dr
    • 合并起来

这里复杂就复杂在合并的时候考虑的情况太多。如果这个点的x坐标和中间数的差值大于d,那么就不用考虑这个点了。也就是说我们仅仅需要考虑如下中间的带状区域里的点:

d=min(dl,dr)
然后需要对灰色带里的两边分别排序,从上到下各自遍历一遍:

  • 遍历的时候,只需要看对面的上下d距离的正方形里有没有点,然后计算距离就好了,这一步的复杂度是O(1)
  • 左遍历一遍,高2d,长度为d的矩形内最多最多边角6个点,因为如果超过6个点就不满足最小距离是d

我虽然理解了,表达实在是费劲,没理解的还是去看上面那篇博客吧

第k大数

仿照快速排序,随机选一个值当做阈值,然后一分为二,如果左边只有k-1个数,那么就选对了;如果一边多一边少,就继续在多的那边选

-------------    你的留言  是我更新的动力😊    -------------