O(logn) 总是一棵树吗？

Question

我们总是看到（二叉搜索）树上的操作在最坏情况下运行时间为 O(logn)，因为树的高度是 logn。我想知道如果我们被告知算法的运行时间是 logn 的函数，例如 m + nlogn，我们是否可以得出结论它必须涉及（增强的）树？

编辑： 感谢您的评论，我现在意识到分治法和二叉树在视觉/概念上非常相似。我从未将两者联系起来。但我想到了一种情况，其中 O(logn) 不是一个分治算法，它涉及一棵没有 BST/AVL/红黑树属性的树。

这是带有 Find/Union 操作的不相交集合数据结构，其运行时间为 O(N + MlogN)，其中 N 是元素数量，M 是 Find 操作的数量。

如果我错过了什么，请告诉我，但我看不出分而治之是如何在这里发挥作用的。我只是在这个（不相交集）情况下看到它有一个没有 BST 属性的树，并且运行时间是 logN 的函数。所以我的问题是为什么/为什么我不能从这个案例中进行概括。

Answer 1

你所拥有的完全是倒退的。 O(lg N) 通常意味着某种分治算法，实现分治的一种常见方法是二叉树。虽然二叉树是所有分而治之算法的一个重要子集，但无论如何它们都是一个子集。

在某些情况下，您可以相当直接地将其他分而治之算法转换为二叉树（例如，对另一个答案的评论已经尝试声称二分搜索是类似的）。然而，仅举另一个明显的例子，多路树（例如 B 树、B+ 树或 B* 树），而显然一棵树显然不是二叉树。

同样，如果您非常想要，您可以扩展一点，即多路树可以表示为二叉树的扭曲版本。如果您愿意，您可能可以将所有例外延伸到说所有例外都是（至少类似）二叉树。然而，至少对我来说，所做的只是使“二叉树”成为“分而治之”的代名词。换句话说，你所做的只是扭曲词汇，从本质上抹掉一个既独特又有用的术语。

Answer 2

不，您还可以对排序数组进行二分搜索（例如）。但不要相信我的话 http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 3

作为一个反例：

given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
    y = y + 1
return y

运行时间是 O(log(n))，但这里没有树！

Answer 4

答案是否定的。已排序数组的二分查找时间复杂度为O(log(n))。

Answer 5

采用对数时间的算法常见在二叉树的操作中。

O(logn) 的示例：

• 使用二分搜索或平衡搜索树在排序数组中查找项目。

• 按二分查找已排序输入数组中的值。

Answer 6

由于 O(log(n)) 只是一个上限，因此所有 O(1) 算法（例如 function (a, b) return a+b; ）都满足条件。

但我必须同意所有 Theta(log(n)) 算法看起来都像树算法，或者至少可以抽象为一棵树。

Answer 7

简短回答：

仅仅因为算法将 log(n) 作为其分析的一部分并不意味着涉及树。例如，以下是一个非常简单的算法，O(log(n)

for(int i = 1; i < n; i = i * 2)
  print "hello";

如您所见，没有涉及树。John 还提供了一个很好的示例，说明如何在这些都需要 O(log(n)) 时间，并且可以创建或引用其他代码示例，因此不要基于渐近时间复杂度做出假设，请查看代码以了解。当然，

更多关于树的信息：

仅仅因为算法涉及“树”并不意味着O(logn)您也需要知道树类型以及操作如何影响。

一些示例：

• 示例 1)

插入或搜索以下不平衡树的时间复杂度为 O(n)。

• 示例 2)

插入或搜索以下平衡树都需要 O(log(n))。

平衡二叉树：

3 阶平衡树：

其他评论

如果您使用的树没有办法“平衡” ”，那么您的操作很可能会花费 O(n) 时间，而不是 O(logn)。如果您使用自平衡树，则插入通常需要更多时间，因为树的平衡通常发生在插入阶段。