不同数据结构的 Big O 运行时间
我尝试计算出以下数据结构的 Big O 运行时间。 它们正确吗？
将 n 个整数插入最初为空的 AVL 树（最佳情况） O(log n)
将 n 个整数插入最初为空的 AVL 树（最坏情况） O(log n)
将 n 个整数插入到最初为空的二叉搜索树中，该二叉搜索树不强制执行 结构特性（最好情况） O(log n)
将 n 个整数插入到最初为空的二叉搜索树中，该二叉搜索树不强制执行 结构特性（最坏情况） O(n)
此外，解释它们为什么不正确也会有所帮助
I've tried to come up with the Big O Running time of the following data structures.
Are they Correct?
Inserting n integers into an initially empty AVL Tree (best case)
O(log n)Inserting n integers into an initially empty AVL Tree (worst case)
O(log n)Inserting n integers into an initially empty binary search tree that does not enforce
structure properties (best case)
O(log n)Inserting n integers into an initially empty binary search tree that does not enforce
structure properties (worst case)
O(n)
Also an explanation as to why they are incorrect would be helpful
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我在这里假设您需要插入所有元素的总时间：
（1）在AVL树的最佳情况，您永远不需要低于根，[即所有元素都相等到根]所以它将是O(n)。 [无论树的大小如何，都不需要加深超过 1 步]。每个元素 O(1)。
(2) AVL树的最坏情况：向AVL树插入n个整数的时间复杂度为O(nlogn)。每一步都是 O(log(T))，其中 T 是当时的大小。 O(log1) + O (log2) + ... + O(logn) = O(log1 + log2 + ... + logn) = O(log(1*...*n)) = O （nlogn）。所以O(nlogn)。每个元素的 O(logn)
(3)，无结构强制，最好的情况，仍然O(n)，与 (1) 的原因相同。在最好的情况下，您添加的所有元素都是根，因此您永远不需要在树中向下查找，无论它的大小是多少。每个元素 O(1)。
(4) 无结构强制，最坏情况：正如其他答案中所述，找到每个元素的位置是 O(n)，因此总的来说，您的最坏时间复杂度为 O(n^2)。每个元素 O(n)。
I am assuming here you need the total time for inserting all the elements:
(1) at best case for an AVL tree, you will never need to go below the root, [i.e. all the elements are equal to the root] so it will be O(n). [never need to deepen more then 1 step, regardless of the tree's size]. O(1) per element.
(2) worst case for AVL tree: inserting n integers to an AVL tree is O(nlogn). each step is O(log(T)) where T is the size at that moment.
O(log1) + O (log2) + ... + O(logn) = O(log1 + log2 + ... + logn) = O(log(1*...*n)) = O(nlogn). so O(nlogn). O(logn) per element(3) with no structure enforce, best case, still O(n), same reason for (1). at best case, all elements you add are exactly the root, so you will never need to go down in the tree, no matter what its size is. O(1) per element.
(4) with no structure enforce, worst case: as said in other answers, finding the place for each element is O(n), so at overall you will have a worst time complexity of O(n^2). O(n) per element.
您的定义不正确：
您无法在少于
n次操作中访问（和复制）n数据项，因为您应该阅读每个项目（因此，O(n)是移动 n 个元素的最低限度）。所以，我的假设是你为单个元素给出了正确的
O()（这有点错误，因为可以在特殊输入上实现最佳效果；你的估计是平均情况，而不是最好的），因此，对于总的描述操作，我将每个乘以O(n)：将 n 个整数插入最初为空的 AVL 树（
最佳情况）O(n*log n)更新：这是平均值；在特殊输入上，最佳时间可能会更低。将 n 个整数插入最初为空的 AVL 树（最坏情况）
O(n*log n)将 n 个整数插入到最初为空的二叉搜索树中，该二叉搜索树不强制执行结构属性（最佳情况）
O(n*log n)更新：这可能取决于实现和整数序列；所以最好的情况是O(n)（参见注释）。将 n 个整数插入到最初为空的二叉搜索树中，该二叉搜索树不强制执行结构属性（最坏情况）
O(n*n)This is incorrect in your definition:
You can't access (and copy)
ndata items in less thannoperations, because you should read each item (so,O(n)is bare minimum of moving on n elements).So, my assumtion is that you give correct
O()for single element (this is a bit wrong, because best can be achieved on special inputs; your estimations are of average case, not the best), so, for total described operation I'll multiply each withO(n):Inserting n integers into an initially empty AVL Tree (
bestcase)O(n*log n)UPDATE: this is the average; best time can be lower on special inputs.Inserting n integers into an initially empty AVL Tree (worst case)
O(n*log n)Inserting n integers into an initially empty binary search tree that does not enforce structure properties (best case)
O(n*log n)UPDATE: this may depend on implementation and on sequence of integers; so best case isO(n)(see comments).Inserting n integers into an initially empty binary search tree that does not enforce structure properties (worst case)
O(n*n)插入
n个整数如何导致O(logn)的大 O。这没有任何意义。当然，读取整数本身至少需要O(n)。因此，对于不平衡的 BST 示例，最坏的情况是插入一个排序的数字列表，例如
1,2,3,4。插入1需要0时间。插入 2 需要~1时间。插入 3 需要~2时间。等等。这相当于1+2+3+...+n = O(n^2)。同样，在最好的情况下，每次后续插入都需要
log(i)时间。所以总的运行时间是log(1)+log(2)+log(3)+...+log(n)。它的评估结果并不是立即显而易见的。但如果你懂一点微积分，你就会发现这（几乎）是 log n 从 1 到 n 积分的梯形规则近似。这大约是nlogn - n = O(nlogn)。我相信您可以对 AVL 树进行类似的分析。
How can inserting
nintegers result in a Big O ofO(logn). That doesn't make any sense. Surely reading the integers itself would take at leastO(n).So for the unbalanced, BST example the worst case is where you insert a sorted list of numbers like
1,2,3,4. Inserting 1 takes 0 time. Inserting 2 takes~1time. Inserting 3 takes~2time. etc. This amounts to1+2+3+...+n = O(n^2).Similarly in the best case scenario, each subsequent insert takes
log(i)time. So the total running time islog(1)+log(2)+log(3)+...+log(n). What this evaluates to is not immediately obvious. But if you know a bit of calculus, you can see that this is (almost) the trapezoidal rule approximation to integral of log n from 1 to n. This is approximatelynlogn - n = O(nlogn).I'm sure you can do similar analysis for the AVL trees.
对不起，但他们都错了。
您使用的是单次插入的 Big-O。如果你做了 n 个，你就必须做 n 次。
所以正确的数字是：
Inserting n integers into:
O(n) - 1 个项目的最佳情况插入时间实际上是 O(1)
O(n^2) - 如果不强制执行结构属性，则可能会得到完全不平衡的树，因此在最坏的情况下，由 n 个元素组成的树的高度为 n =>你的树将变形为一个列表。
I'm sorry, but they are all wrong.
what you used are the Big-Os for a single insertion. If you do n of them, you have to take that times n.
So the correct figures are:
Inserting n integers into:
O(n) - The best case insertion time for 1 item is actually O(1)
O(n^2) - if you do not enforce structure properties, you might end up with a completely unbalanced tree, so in the worst case your tree of n elements has a height of n => Your tree will deform into a list.
是的，你是对的，如果你把所有的东西都乘以n。您的运行时间是针对一个元素的。
Yes, you're correct, if you multiply everything with n. Your running time is for one element.