预览加载中，请您耐心等待几秒...

算法合集之《分治算法在树的路径问题中的应用》.ppt

预览
1/10
2/10
3/10
4/10
5/10
6/10
7/10
8/10
9/10
10/10

亲，该文档总共50页，到这已经超出免费预览范围，如果喜欢就直接下载吧～

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

分治算法 在树的路径问题中的应用论文内容一、树的分治算法两种常见的形式两种常见的形式两种常见的形式两种常见的形式效率分析【例一】树中点对统计一条路径：记D(i)表示节点i到根节点路径的长度时间复杂度分析二、路径剖分算法轻重边路径剖分【例二】QueryOnaTreeⅣ路径剖分算法路径剖分与树的分治的联系路径剖分与树的分治的联系QueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣQueryOnaTreeⅣ时间复杂度分析三、树的分治算法的进一步探讨如何改进基于边的分治的时间复杂度如何改进基于边的分治的时间复杂度如何改进基于边的分治的时间复杂度如何改进基于边的分治的时间复杂度使用基于边的分治解决上题使用基于边的分治解决上题时间复杂度分析总结谢谢大家算法的常数算法的常数算法的常数树的重心定理：存在一个点使得分出的子树的结点个数均不大于N/2