- 论坛徽章:
- 0
|
本帖最后由 wingforce 于 2011-09-23 16:37 编辑
在“不对树的结构做任何假设的情况下”，所谓最差情况的2亿循环是根本没法避免的。
没有深度信息，或排序性，或平衡性，又或者类似线索树的复杂结构，这个问题最终会简化为
“求2个单向链表的交点”
- 这个也可以同时解决和解释前面有人说的，如果2个结点没有共同祖先，在这个模型下就是2条不相交的单向链表
- 这和树是2叉还是n叉都没有关系
而这个问题的时间复杂度无论如何不会低于O(n + m), n和m分别是2个单向链表到他们交点的距离，n + m最差情况就是树的结点总数。
每个结点上保存深度也好，小狗爬爬也好，或者是把其中一条路线存储起来查询也好，本质来说空间复杂度都是O（n），n是选取的那条路径的长度，最差情况就是树的结点总数。
每个结点保存深度和小狗爬都是额外信息保存在结点内部，其实依然额外消耗的空间
存储起来查询，要解决的问题是查询加速，无论hash还是什么树，都会很难做到O（1）时间获得查询结果。
各种查询树的查询复杂度都不能超过O（logn），这样算法的时间复杂度是O（n × logn）
hash看起来很美，理论上是O（1），实际上由于hash存在冲突的情况，比较难以分析。理想情况的总复杂度是O（n）。实践中，因为前面说的存在冲突情况，会大于O（n）。如果我没记错，为解决冲突，实际上会是n的一个大于1，小于2的幂次，大概这样O（1 ^ 1.0xxx）
所以，如果需要最理想的O（1）空间复杂度，以及和上面所有方法一样的O（n）时间复杂度
先计算2个结点的深度，再使用游标保存当前所指向的结点，才可以“不做任何假设”的，“最优”的空间和时间复杂度解决这个问题。
因为计算2个结点深度的时间复杂度依然是O（n+m），再根据深度求交点的步骤的复杂度也是O（n+m）
所有他们的和没有变，O（n+m） |
|
免费注册
楼主: snowboy9859
发表于 2011-09-22 17:14
发表于 2011-09-22 20:05
是单线程回合制还是开双线程实现？