O（logn）总是一棵树吗？
由于树高为logn，我们总是看到（二叉搜索）树上的操作具有O（logn）最差情况下的运行时间。 我想知道是否有人告诉我们一个算法的运行时间是logn的函数，例如m + nlogn，我们可以得出结论：它必须包含一个（增广的）树吗？
编辑：感谢您的意见，我现在认识到分治和二叉树在视觉上/概念上非常相似。 我从来没有在两者之间建立过联系。 但是我想到的情况是O（logn）不是一个分治算法，它涉及一棵没有BST / AVL /红黑树属性的树。
这是具有Find / Union操作的不相交集合数据结构，其运行时间是O（N + MlogN），其中N是元素的数量，M是查找操作的数量。
请让我知道如果我失踪了，但我看不出分治如何发挥作用。 我只是在这个（不相交集）案例中看到它有一棵没有BST属性的树，并且运行时间是logN的函数。 所以我的问题是关于为什么/为什么我不能从这种情况进行概括。
你有什么是完全倒退。 O(lg N)通常意味着某种分而治之的算法，实现分而治之的一种常见方式是二叉树。 虽然二叉树是所有分治算法的重要子集，但无论如何它们都是子集。
在某些情况下，您可以将其他分治算法直接相当直接地转换为二叉树（例如，对另一个答案的评论已经尝试声明二分搜索类似）。 但是，另一个明显的例子是多路树（例如B树，B +树或B *树），而树明显不是二叉树。
同样，如果你想足够糟糕，你可以扩展一个多维树可以表示为二叉树的变形版本。 如果你愿意的话，你可以扩展所有的例外，以说明它们全都是（至少类似于）二叉树。 但至少对我来说，所做的一切就是让“二叉树”与“分而治之”的同义词。 换句话说，你所完成的只是歪曲词汇，并且基本上抹杀了一个既独特又有用的术语。
不，你也可以二进制搜索一个有序数组（例如）。 但不要拿我的话来说http://en.wikipedia.org/wiki/Binary_search_algorithm
作为反例：
given array 'a' with length 'n'
y = 0
for x = 0 to log(length(a))
y = y + 1
return y
运行时间是O（log（n）），但没有树在这里！
链接地址: http://www.djcxy.com/p/40009.html