O（logn）总是一棵树吗？
https://stackoverflow.com/questions/2308779
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
我们总是在（二进制搜索）树上看到操作，因为树高为logn，因此具有O（logn）最差的情况下运行时间。我想知道我们是否被告知算法的运行时间是logN的函数，例如m + nlogn，我们可以得出结论，它必须涉及（增强）树吗？
编辑：多亏了您的评论，我现在意识到划分和二进制树在视觉/概念上是如此相似。我从未在两者之间建立联系。但是我想到的是，o（logn）不是涉及没有BST/AVL/Red-Black树特性的树的划分算法的情况。
这就是与查找/联合操作的脱节数据结构，其运行时间为O（n + mlogn），n是元素的＃和查找操作的数量。
请让我知道我是否错过了STH，但是我看不到分裂诱因是如何在这里发挥作用的。我只是在此（不相交的情况）中看到它具有没有BST属性的树，并且运行时间是LOGN的函数。因此，我的问题是为什么/为什么不从这种情况下进行概括。
解决方案
您拥有的完全是向后的。 O(lg N) 通常意味着某种形式的分歧和征服算法，而实施分裂和征服的一种常见方法是二进制树。虽然二进制树是所有分隔算法的大量子集，但无论如何都是子集。
在某些情况下，您可以将其他鸿沟和征服算法直接转换为二进制树（例如，对另一个答案的评论已经尝试声称二进制搜索是相似的）。但是，仅出于另一个明显的例子，是一棵多路树（例如A 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）），但这里没有树！
答案是否定的。对排序阵列的二进制搜索是 O(log(n)).
花时间的算法是 通常 在二进制树上的操作中发现。
o（logn）的示例：
在带有二进制搜索或平衡搜索树的分类数组中找到一个项目。
通过分分为一分类的输入阵列中查找值。
因为o（log（n））只是上限，也是所有o（1）算法 function (a, b) return a+b; 满足情况。
但是我必须同意所有theta（log（n））算法看起来像树算法，或者至少可以将其抽象到树上。
简短答案：
仅仅因为算法作为其分析的一部分具有log（n）并不意味着涉及树。例如，以下是一种非常简单的算法 O(log(n)
for(int i = 1; i < n; i = i * 2)
print "hello";
如您所见，没有涉及树。约翰，还提供了一个很好的例子，说明如何在排序的数组上进行二进制搜索。这两者都需要O（log（n））时间，并且还有其他代码示例可以创建或引用。因此，不要根据渐近时间复杂性做出假设，请查看确定要了解的代码。
有关树的更多信息：
仅仅因为算法涉及“树”并不意味着 O(logn) 任何一个。您需要知道树类型以及操作如何影响树。
一些例子：
- 示例1）
插入或搜索以下不平衡树将是 O(n).
- 示例2）
插入或搜索以下平衡的树将通过 O(log(n)).
平衡的二进制树：
平衡树3：
附加评论
如果您使用的树木没有办法“平衡”，那么您的操作很有可能 O(n) 时间没有 O(logn). 。如果您使用自我平衡的树木，则插入通常需要更多的时间，因为在插入阶段通常会出现树木的平衡。
