Llf's blog

标签 点分治 下的文章

April 26, 2018

点分治总结

我自己感觉点分治是一种比较玄学神奇的算法,感觉自己也只是理解了一点皮毛而已。这里就谈谈点分治的实现方法和一些运用。 方法 点分治其实是将一棵树的点不断分为多棵子树,分别得到子树节点到子树根的距离来进行处理。 既然要有一个点为根节点,那么应该选取哪一个点呢? 既然要向下分治,如果把一个原来的叶节点作为分治的根节点,那么遍历每一个点的时间开销是非常大的。然而如果这个点的左右子树都达到最大,那么...