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))，但这里没有树！