随机抽取数组元素k次,从最接近搜索元素x 的位置顺序搜索, 顺序搜索的平均比较次数为O(n/(k+1)).
举一反三
- 假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为（ ）。
- 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度
- 若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同?搜索失败;
- ●采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为 (36) 。(36) A: n B: n／2 C: (n-1)／2 D: (n+1)／2
- 类比二分搜索算法，设计k 分搜索算法（k 为大于2 的整数）如下：首先检查n / k 处（n为被搜索集合的元素个数）的元素是否等于要搜索的值，然后检查2n / k 处的元素，…，这样，或者找到要搜索的元素，或者把集合缩小到原来的1/ k ；如果未找到要搜索的元素，则继续在得到的集合上进行k 分搜索；如此进行，直到找到要搜索的元素或搜索失败。此k 分搜索算法在最坏情况下搜索成功的时间复杂度为 （64） ，在最好情况下搜索失败的时间复杂度为 （65） 。 （65）处填（）。 A: O(log n) B: O(nlog n) C: O(logk n) D: O(nlogk n)