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

回答

相關問題