从一棵空树开始，以大 O 表示法插入红黑树的复杂性是多少？
如果我有 10 个元素并从一棵空树开始，以大 O 表示法将 10 个元素插入红黑中的复杂性是多少？
是否会超过 O(log 10)，因为每次插入元素时，它都必须搜索该元素的适当位置，并在祖先节点和子节点之间执行一系列旋转。因此，如果我有 N 个元素并在红黑树中插入 N 次，那么这不是 O(n log n) 吗？
感谢您的任何帮助。
If I have 10 elements and starting with an empty tree, What is the complexity of inserting 10 elements into Red Black in big-O notation?
Is it going to be more than O(log 10) because each time it inserts an element, it has to search for appropriate location for the element and performs a series of rotations between ancestor nodes and child nodes. So if I have N element and inserting N times into Red Black Tree, wouldn't that make it O(n log n)?
Thanks for any help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你永远不会将大 O 与常量（1 除外）一起使用，因为 O(10) 的含义与 O(1) 或 O(128291) 完全相同，因此按照惯例，你总是使用 O(1)！
那么，让我们看看将 K 个项目插入到最初为空的 RB 树中的大 O 是什么。第一次插入的时间是常数，所以称之为 O(1)；当有 X 个项目时插入 X+1 是 O(log(X)) （即使你必须向下旋转每一步，它仍然是与 log(X) 成比例的最坏情况，所以，O(log(X) ），因为“层”或“级别”的数量仅随 X 呈对数增长——因为 K 层的 RB 树的节点数量以 2 的 K 次方增长）。
因此，我们想要 X 从 2 到 N（加上常量）的 log(X) 总和，它恰好等于 N 的阶乘的对数。 org/wiki/Stirling's_approximation" rel="nofollow noreferrer">斯特林近似，大约是 N log(N) - N，用大 O 术语又可以归结为 N log(N)。
You never use big-O with a constant (except 1) because O(10) means exactly the same as O(1) or O(128291), so by convention you always use O(1)!
So, let's see what's the big-O of inserting K items into an initially empty RB-tree. The first insertion is a constant time so call it O(1); and inserting when there are X items the X+1st is O(log(X)) (even if you have to rotate each step down, it's still worst-case proportional to log(X), so, O(log(X)), because the number of "layers", or "levels", only grows logarithmically with X -- since an RB tree for K levels has a number of nodes that grows as 2 to the Kth power).
So we want the summation of log(X) for X from 2 to N (plus a costant), which happens to be equal to the log of the factorial of N. Per Stirling's approx, that's about N log(N) - N, which in big-O terms boils down to N log(N) again.
@Justice 和 @Alex 真正想要表达的是，
O(f(N))复杂性度量讨论了限制行为（例如运行时间、比较次数等），因为 N 倾向于无穷大。他们说，如果用特定值替换 N，
O术语就不再有意义。还有一点他们没有提出。也就是说，您不能使用
O(...)表示法来告诉您当 N 很小时会发生什么。根据定义，“大 O”符号不会告诉您在这种情况下会发生什么。这不仅仅是迂腐。例如，成本函数
F(N) = 1,000,000 * N + N**2为O(N**2)，但对于 N 的值，第一项占主导地位少于 1,000。在这种情况下，如果您尝试使用O(N**2)度量作为估计器，您将得到完全错误的答案。What @Justice and @Alex are really getting at is that a
O(f(N))complexity measure talks about the limiting behavior (e.g. time to run, number of comparisons, whatever) as N tends to infinity.They are saying that if you substitute a particular value for N, the
Oterminology is no longer meaningful.There is another point that they didn't make. That is that you cannot use a statement in
O(...)notation to tell you what happens when N is small. By definition "big O" notation tells you nothing about what happens in that case.This is not just pedantry. For example the cost function
F(N) = 1,000,000 * N + N**2isO(N**2), but the first term dominates for values of N less than 1,000. If you try to use theO(N**2)measure as an estimator in this case, you will get totally the wrong answer.将单个元素插入 RB 树的时间复杂度为
O(log n)，其中n是树的当前大小。因此，将
n个元素插入空 RB 树的时间复杂度为O(n log n)。将
10元素插入空 RB 树的时间复杂度是恒定的，即O(1)。因为树一开始是空的，而且插入的元素数量是固定的，所以这里没有可变元素。The time-complexity of inserting a single element into an RB-tree is
O(log n)wherenis the current size of the tree.The time-complexity of inserting
nelements into an empty RB-tree is, therefore,O(n log n).The time-complexity of inserting
10elements into an empty RB-tree is constant, orO(1). Because the tree starts empty, and because the number of elements being inserted is fixed, there are no variable elements here.