在一棵有n*2^n个元素的平衡二元搜索树中搜索一个元素,最坏的情况下运行时间是多少?

问题描述 投票:0回答:1

我知道搜索一棵有n个节点的平衡树是O(logN),但我甚至不知道为什么问题中所说的树也是一棵平衡二叉树。

algorithm tree binary-search-tree
1个回答
3
投票

好吧,就像你说的,一个有k个节点的平衡BST的查找时间是O(log k)。所以我们要做的就是插入n2n 对于k,看看我们得到了什么。

对数(n2n)

= log n + log 2n

= log n + n log 2

= O(n)。

这也是有道理的,因为一棵树上的节点数量是指数级的,用对数时间算法打出的树应该是线性时间。

© www.soinside.com 2019 - 2024. All rights reserved.