comparison

Considering this post which says: “big O时间三值Search是Log_3ň而非二进制Search的Log_2 N”comparison

这应该是因为classical ternary搜索将需要3个比较instead两个，而是将这项实现比二元搜索更无效吗？

#!/usr/bin/python3 

List = sorted([1,3,5,6,87,9,56, 0]) 
print("The list is: {}".format(List)) 

def ternary_search(L, R, search): 
    """iterative ternary search""" 

    if L > R: 
     L, R = R, L 
    while L < R: 

     mid1 = L + (R-L)//3 
     mid2 = R - (R-L)//3 

     if search == List[mid1]: 
      L = R = mid1 
     elif search == List[mid2]: 
      L = R = mid2    
     elif search < List[mid1]: 
      R = mid1 
     elif search < List[mid2]: 
      L = mid1 
      R = mid2 
     else: 
      L = mid2 

    if List[L] == search: 
     print("search {} found at {}".format(List[L], L)) 
    else: 
     print("search not found") 


if __name__ == '__main__': 
    ternary_search(0, len(List)-1, 6)

该实现在每次迭代中只有两次比较有效。那么，忽略计算中点所需的时间，是不是会像二分查找那样有效？

那么为什么不把这个进一步进行一个n-ary搜索？（尽管我不知道这是否是正确答案），然而，搜索的主要关注点是中点计算的数量而不是比较的数量，尽管我不知道这是否是正确的答案。

来源

2017-10-15 mathmaniage

由于** O（log_2 N）= O（log_3 N）**，您提到的帖子是没有意义的。但答案是正确的。如果你做对了，二进制搜索在最坏的情况下比较少。 –

[Binary Search vs Ternary Search]可能的重复（https://stackoverflow.com/questions/32572355/binary-search-vs-ternary-search） –

@MattTimmermans，上面我已经指出了三元搜索如上每次迭代只做两次比较，所以，在最坏的情况下，这样做会不会相同？ – mathmaniage

尽管两者都具有对数复杂度，但三元搜索将快于二叉搜索足够大的树。

虽然二进制搜索每个节点比较少一个，但它比三元搜索树更深。对于有1亿个节点的树，假设两棵树都有适当的平衡，BST的深度将是〜26，对于三元搜索树来说它的深度是〜16。再一次，除非你有一棵很大的树，否则这种加速将不会被感觉到。

对下一个问题的回答“为什么不进一步进行n-ary搜索？”很有趣。实际上有些树木需要进一步研究，例如b-tree和b + -tree。它们大量用于数据库或文件系统，并且可以有100-200个从父节点产生的子节点。

为什么？因为对于这些树，您需要为您访问的每个节点调用IO操作;你可能意识到成本很高，比你的代码执行的内存操作要多得多。因此，尽管您现在必须在每个节点执行n-1个比较，但是这些内存操作的成本与IO成本与树的深度成比例的成本相比是微不足道的。对于内存操作，请记住，当你有n个元素的n元树时，基本上有一个数组，它具有O（n）的搜索复杂度，因为所有元素现在都在同一个节点中。所以，在增加ary的同时，它会停止更高效并开始实际损害性能。

那么，为什么我们总是比较喜欢BSt，即2-ary而不是3或4，或者这样呢？因为实施起来很简单。这是真的，这里没有什么大不了的。

来源

2017-10-18 17:58:27

回答

相关问题