本文发表在 rolia.net 枫下论坛O(n)是找到一个ancestor的时间,找到所有ancestor for the given person需要O(n^2).
找到所有的ancestor 就是个遍历2叉树的时间复杂度, 咋能算出来 n^2 呢?
ok. 打个比方 从建好的一个ancestor 的2叉树 中, 找到一个特定的节点的ancestor 这个时间复杂度是 O(n) 吧?
然后我可以把这个节点当做一个root 返回到function 外面吧?
Node * getNode( BST * aNode ) --------------> 查找一个特定的节点.
{
....
}
aRoot = getNode( BST * aNode ); ---------> 找到特定节点赋值给 aRoot
void printAncestor( aRoot ) ------------------> 遍历aRoot的 2叉树 打印出来所有的ancestors
{
.....
display aNode;
....
}
这个时间复杂度就是O(n) 不知道咋能是 n square 呢? 就是个遍历 n 个节点的过程. 你的函数的输入节点数并没有增加, 而且我的节点只是被遍历一次.(当然我里面有动态编程的优化,保证一个节点只是被遍历一次)
为何是 n suqare 呢?
你的BST是要找所有ancestor的吧?你是把结果存到了二叉树里面,二叉树本身的优势没有起到作用。不如直接扫list,顺带输出
----- 我的BST 或者说 不能说是 BST. 其实 就是个简单的2叉树而不是 Binary Search Tree. 我是通过用户的输入构造的2叉树.
构造好了 再遍历找一个特定的person的 祖先.
你说的直接扫 list? 你说的这个list 是啥list? 就是不管啥关系只要是祖先就往这个list 里面塞? 一个人的爷爷往里面塞, 爸爸往里面塞, 只要是>他上一辈儿的都往这个list 里面塞?
是这个意思吗? 还是 ....?更多精彩文章及讨论,请光临枫下论坛 rolia.net