有人知道如何计算嵌套二进制搜索树的复杂度吗?我已经实现了一个嵌套的二进制搜索树,深度达到3个BST.
对于造成混淆,我深表歉意,我的意思是BST的每个节点都指向另一个BST的根节点.我要求的复杂性是搜索,更新和删除(基本操作)的时间复杂性.我曾经假设,由于BST的时间复杂度为O(log(n)),因此嵌套BST的时间复杂度在搜索,更新和删除方面不会有太大差异.
解决方案我假设嵌套"是指一棵特定树的每个节点都指向另一棵树的根,最多三层./p>
二叉搜索树通常将是O(log n)查找时间.由于您要进行3次查找,因此为O(日志a *日志b *日志c).当然,这是假设它们平衡良好,并且一切正常.对于二叉搜索树,最坏的情况是O(n)(想想一棵基本上是一条直线的树).那么最坏的情况是O(a * b * c).
根据记录,a b和c分别是第一棵树,第二棵嵌套树和第三棵双嵌套树中的元素数.
Does anyone know how to calculate the complexity of a nested binary search tree? I have implemented a nested binary search tree to a depth of 3 BSTs.
EDIT: I apologize for the confusion, I had meant that each node of the BST would point to the root node of another BST. The complexity I was asking for was time complexity of search, update, and delete (basic operations). I had assume that since the time complexity of a BST was O(log(n)), the time complexity of a nested BST in terms of search, update, and delete wouldn't differ that much.
解决方案I'm assuming that by "nested" you mean that each node of a particular tree points to the root of another tree, up to 3 levels deep.
Well a binary search tree is generally going to be O(log n) lookup time. Since you're doing 3 lookups, that's O(log a * log b * log c). Of course that's assuming that they're well balanced and everything. The worst case for a binary search tree is O(n) (think of a tree where it's basically a straight line). Then the worst case time would be O(a * b * c).
And for the record, a b and c are the number of elements in the first tree, second nested tree, and third doubly-nested tree, respectively.
更多推荐
嵌套二叉搜索树的复杂性
发布评论