mou*_*sey 39 algorithm binary-tree data-structures ternary-tree
我最近听说过三元搜索,我们将一个数组分成3个部分进行比较.这里将进行两次比较,但它将数组减少到n/3.人们为什么不用这么多？
Bor*_*lid 42
实际上,人们确实使用k-ary树来获得任意k.
然而,这是一个权衡.
要在k-ary树中查找元素,需要围绕k*ln(N)/ ln(k)运算(记住基础变化公式).k越大,您需要的整体操作就越多.
你所说的逻辑扩展是"为什么人们不为N数据元素使用N-ary树？".当然,这将是一个阵列.
Aku*_*ete 26
三元搜索仍将为您提供相同的渐近复杂度O(log N)搜索时间,并增加了实现的复杂性.
可以说同样的论点,为什么你不想要四元搜索或任何其他更高的顺序.
Mic*_*urr 25
搜索10亿(10亿 - 1,000,000,000)个分类项目与二元搜索相比平均约为15个,而三元搜索比较大约9个 - 这不是一个巨大的优势.请注意,每次'三元比较'可能涉及2次实际比较.
哇.我认为,最受欢迎的答案会错过这个问题.
您的CPU不支持三元逻辑作为单个操作; 它将三元逻辑分解为二进制逻辑的几个步骤.CPU的最佳代码是二进制逻辑.如果芯片是常见的,支持三元逻辑作为单一操作,那么你是对的.
B树在每个节点上可以有多个分支; order-3 B-tree是三元逻辑.树中的每一步都将进行两次比较,而不是一次,这可能会导致CPU时间变慢.
然而,B树很常见.如果你假设树中的每个节点都将分别存储在磁盘上的某个地方,那么你将花费大部分时间从磁盘读取......并且CPU不会成为瓶颈,但磁盘将是.因此,您可以选择每个节点有100,000个子节点的B树,或者其他任何几乎不适合一个内存块的子树.具有这种分支因子的B树很少会超过三个节点,并且您只需要三个磁盘读取 - 三个停止瓶颈 - 来搜索庞大而庞大的数据集.
回顾:
小智 8
是什么让你认为三元搜索应该更快？
平均比较次数:
in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
最差的比较数:
in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search = 1 * ln(n)/ln(2) ~ 1.443*ln(n).
所以看起来三元搜索更糟糕.
三元搜索比二分搜索更快的唯一方法是,如果可以以低于双向比较成本的1.55倍的方式进行3向分区确定.如果项目存储在排序数组中,则3路确定平均为双向确定的1.66倍.但是,如果信息存储在树中,则获取信息的成本相对于实际比较的成本较高,而缓存局部性意味着随机获取一对相关数据的成本并不比获取单个数据的成本差得多.数据,三元树或n路树可以大大提高效率.
另外，请注意，如果我们继续下去，这个序列会推广到线性搜索
Binary search
Ternary search
...
...
n-ary search ? linear search
因此，在 n 元搜索中，我们将有“一个唯一的比较”，这可能需要多达 n 次实际比较。