algorithm - 二叉树的大 O 表示法

Question

我的教科书说在二叉树中查找节点的大 O 表示法是 O(log ₂ N)，如果N = 1log ₂ N 为 0，这是不可能的吗？这会被四舍五入1还是还有更多？

score 5 · Accepted Answer

Big-O 表示法旨在描述当数据量（或任何N描述的内容）向无穷大增加时算法的执行时间（或内存消耗，或......）如何扩展。当给定N. 在的值较低的情况下N，常数因素往往会占主导地位。在这种情况下，您要得出的只是该特定算法的执行时间以对数方式缩放。

score 4 · Accepted Answer

O 表示法只关心 N 趋于 ∞ 时的限制行为。形式上，如果存在一个常数 C 和另一个常数 N，则非负函数 f 属于 O(g(n)) 类，使得

n ≥ N ⇒ f(n) ≤ C g(n).

常数因子和小 n 值根本不重要。

score 1 · Accepted Answer

O首先，在节点的二叉树中找到一个节点N的说法O(log N)是错误的。该陈述适用于二叉搜索树，但不适用于一般二叉树。

如果 N = 1，那么 log N 将为 0，这是不可能的吗？这会被四舍五入到 1 还是还有更多？

没关系。说f大O(log n)就是说有一个常数C，N所以

n >= N implies f(n) <= C * g(n)

即，最终 f以为界C * g。因此，对于有限数量的值（包括n = 0. 那是O关于描述渐近行为，而不是所有行为。

score 1 · Accepted Answer

大 O 是渐近复杂度 - 实际运行时间类似于 log ₂ N + C，所以N = 1你的运行时间为C

score 1 · Accepted Answer

是的，它将仅为零，但您必须首先决定要在哪个上下文中讨论它。如果您查看 BigO 的定义，则无需替换 N 的值，只需尝试了解更糟的情况。

但是如果你从时间的角度考虑，当树中只有一个节点时，就没有什么可搜索的了。

最后但并非最不重要的一点是，此 log(n) 时间复杂度适用于平衡二叉搜索树，而不适用于普通二叉树。

5 回答 5