Mar*_*n08 6 algorithm tree big-o binary-search-tree
我们总是看到(二元搜索)树上的操作具有O(logn)最差情况下的运行时间,因为树高是logn.我想知道我们是否被告知算法的运行时间是logn的函数,例如m + nlogn,我们可以得出结论它必须涉及(增强的)树吗？
编辑:感谢您的评论,我现在意识到分治和二叉树在视觉/概念上是如此相似.我从来没有在两者之间建立联系.但我想到一个案例,其中O(logn)不是一个分治算法,它涉及一棵没有BST/AVL /红黑树属性的树.
这是具有查找/联合操作的不相交的集合数据结构,其运行时间为O(N + MlogN),其中N是元素的数量,M是查找操作的数量.
如果我错过了,请告诉我,但我看不出分治在这里如何发挥作用.我只是在这个(不相交的集合)情况下看到它有一个没有BST属性的树,而运行时间是logN的函数.所以我的问题是为什么/为什么我不能从这个案例中进行推广.
不,您也可以二进制搜索已排序的数组(例如).但是不要相信我的话http://en.wikipedia.org/wiki/Binary_search_algorithm
你所拥有的只是倒退.O(lg N)通常意味着某种分而治之的算法,实现分而治之的一种常用方法是二叉树.虽然二叉树是所有分而治之算法的重要子集,但无论如何都是子集.
在某些情况下,您可以将其他划分和征服算法直接转换为二叉树(例如,对另一个答案的评论已经尝试声称二进制搜索类似).然而,仅仅为了另一个明显的例子,一个多路树(例如B树,B +树或B*树),而显然一棵树显然不是二叉树.
同样,如果你想要足够严重,你可以扩展多点树可以表示为二进制树的扭曲版本的点.如果你愿意,你可以扩展所有的例外,以便说它们都是(至少是类似的)二叉树.然而,至少对我来说,所做的就是让"二叉树"成为"分而治之"的代名词.换句话说,你所完成的只是扭曲词汇,基本上抹掉了一个既独特又有用的术语.