三元搜索比二分搜索更糟糕？

Question

人们通常会问这个问题的反面(三元搜索是否优于二元搜索？).

我真的认为情况更糟(不是在O(log n)的复杂性方面).我真的不善于数学,只是纯粹的直觉.

如果我们采用大小为n的数组并使用二进制搜索,在第一次比较之后我们有n/2问题大小,并且在第二次比较之后我们有n/4的问题大小.

通过三元搜索,第一个循环运行已经进行了2次比较!我们的问题大小为n/3.

我是对的还是我错过了什么？在我阅读的所有内容中,人们通常会考虑到三元搜索的第一个循环运行是1比较,我认为这是错误的.

Answer 1

作为一个有趣的练习,让我们考虑一下d-ary搜索,在这里您可以看到(d - 1)数组中均匀间隔的元素,然后决定递归下降到d个不同区间中的哪一个.如果使用d-ary搜索,则每个点保留的数组大小将为n,n/d,n/d ²,n/d ³,...,n/d ^k,.... 这意味着,将被登录_d在递归n个层.在每一层,你进行精确的d - 1比较.这意味着所进行的比较总数为(d-1)log _d n.对于d的任何固定值,这是O(log n),尽管常数因子是不同的.

使用二分搜索,d = 2,并且比较的数量将是(大致)(2 - 1)log ₂ n = log ₂ n.为简单起见,我们将其写为ln n/ln 2 = 1.443 ln n作为自然对数.

使用三元搜索,d = 3,并且比较的数量将是(大致)(3 - 1)log ₃ n = 2 log ₃ n.将其写为自然对数,我们得到这是2 ln n/ln 3 = 1.820 ln n.因此,三元搜索中的比较次数确实大于二进制搜索中的比较次数,因此您希望它比二次搜索慢.实际上,正如本文所指出的那样,这就是实践中发生的事情.

希望这可以帮助!