首页 文章

O（logn）总是一棵树吗？

提问于
浏览 次
6

我们总是看到（二元搜索）树上的操作具有O（logn）最差情况下的运行时间，因为树高是logn . 我想知道我们是否被告知算法的运行时间是logn的函数，例如mnlogn，我们可以得出结论它必须涉及（增强的）树吗？

编辑：感谢您的评论，我现在意识到分治和二叉树在视觉/概念上是如此相似 . 我从来没有在两者之间 Build 联系 . 但我想到一个案例，其中O（logn）不是一个分治算法，它涉及一棵没有BST / AVL /红黑树属性的树 .

这是具有查找/联合操作的不相交的集合数据结构，其运行时间为O（N MlogN），其中N是元素的数量，M是查找操作的数量 .

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

algorithm tree big-o binary-search-tree

7 回答

  • 0

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

    在某些情况下，您可以将其他划分和征服算法直接转换为二叉树（例如，对另一个答案的评论已经尝试声称二进制搜索类似） . 然而，仅仅针对另一个明显的例子，多路树（例如B树，B树或B *树），而显然树也明显不是二叉树 .

    同样，如果你想要足够严重，你可以扩展多点树可以表示为二叉树的扭曲版本的点 . 如果你愿意，你可以扩展所有的例外，以便说它们都是（至少是类似的）二叉树 . 然而，至少对我来说，所做的就是让“二叉树”成为“分而治之”的代名词 . 换句话说，你所完成的只是扭曲词汇并基本上抹掉了一个既独特又有用的术语 .

    回复于
  • 0

    不，您也可以二进制搜索已排序的数组（例如） . 但是不要相信我的话http://en.wikipedia.org/wiki/Binary_search_algorithm

    回复于
  • 0

    作为反例：

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

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

    回复于
  • 7

    答案是否定的 . 二进制搜索已排序的数组是 O(log(n)) .

    回复于
  • 2

    采用对数时间的算法在二叉树的操作中找到 commonly .

    O（logn）的例子：

    • 使用二分搜索或 balancer 搜索树查找已排序数组中的项 .

    • 通过二分查找已排序的输入数组中的值 .

    回复于
  • 7

    由于O（log（n））仅是上限，所以所有O（1）算法（如 function (a, b) return a+b; ）都满足条件 .

    但我不得不同意所有的Theta（log（n））算法看起来像树算法，或者至少可以抽象到树上 .

    回复于
  • 3

    Short Answer:

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

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

    如您所见，没有涉及树 . John还提供了关于如何在排序数组上完成二进制搜索的一个很好的例子 . 这些都需要O（log（n））时间，并且还有其他可以创建或引用的代码示例 . 所以不要根据渐近时间复杂度做出假设，看看代码就知道了 .

    More On Trees:

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

    Some Examples:

    • Example 1)

    插入或搜索以下不 balancer 树将是 O(n) .

    enter image description here

    • Example 2)

    插入或搜索以下 balancer 树都是 O(log(n)) .

    balancer 二叉树：

    enter image description here

    3级 balancer 树：

    enter image description here

    Additional Comments

    如果您正在使用的树木没有办法，那么您的作业很可能不会 O(n) 时间 O(logn) . 如果使用自 balancer 树，则插入通常需要更多时间，因为树的 balancer 通常在插入阶段发生 .

    回复于

相关问题