c - 从一棵空树开始，以大 O 表示法插入红黑树的复杂度是多少？

Question

如果我有 10 个元素并从一棵空树开始，以大 O 表示法将 10 个元素插入 Red Black 的复杂性是什么？

是否会超过 O(log 10)，因为每次插入元素时，它都必须为元素搜索适当的位置，并在祖先节点和子节点之间执行一系列旋转。因此，如果我有 N 个元素并在 Red Black Tree 中插入 N 次，那不是 O(n log n) 吗？

谢谢你的帮助。

Answer 1

你永远不会使用带常量的 big-O（除了 1），因为 O(10) 的含义与 O(1) 或 O(128291) 完全相同，所以按照惯例，你总是使用 O(1)！

那么，让我们看看将 K 个项目插入到最初为空的 RB-tree 中的大 O 是什么。第一次插入是一个常数时间，所以称之为 O(1)；并在有 X 个项目时插入 X+1st 是 O(log(X)) （即使你必须向下旋转每一步，它仍然是与 log(X) 成正比的最坏情况，所以，O(log(X) )，因为“层”或“层”的数量仅与 X 成对数增长——因为 K 层的 RB 树的节点数量增长为 2 的 K 次方）。

所以我们想要 X 从 2 到 N 的 log(X) 的总和（加上一个常数），它恰好等于 N 的阶乘的对数。根据斯特林的 approx，大约是 N log(N) - N，在大 O 术语中，它再次归结为 N log(N)。

Answer 2

@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)度量作为估计量，您将得到完全错误的答案。

Answer 3

将单个元素插入 RB 树的时间复杂度是树O(log n)的n当前大小。

n因此，将元素插入空 RB 树的时间复杂度为O(n log n)。

10将元素插入空 RB 树的时间复杂度是恒定的，或O(1). 因为树一开始是空的，而且插入的元素数量是固定的，所以这里没有可变元素。