2

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

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

谢谢你的帮助。

4

3 回答 3

9

你永远不会使用带常量的 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)。

于 2009-11-15T03:44:57.270 回答
2

@Justice 和@Alex 真正得到的是,O(f(N))复杂性度量讨论了限制行为(例如运行时间、比较次数等),因为 N 趋于无穷大。

他们说如果你用一个特定的值代替 N,这个O术语就不再有意义了。

还有一点他们没有提出。也就是说,您不能使用O(...)符号中的语句来告诉您当 N 很小时会发生什么。根据定义,“大 O”符号不会告诉您在这种情况下会发生什么。

这不仅仅是迂腐。例如,成本函数F(N) = 1,000,000 * N + N**2O(N**2),但对于 N 小于 1,000 的值,第一项占主导地位。如果您在这种情况下尝试使用O(N**2)度量作为估计量,您将得到完全错误的答案。

于 2009-11-15T04:21:46.497 回答
1

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

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

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

于 2009-11-15T03:41:20.260 回答