单选题 软件设计师
题号 #584772

根据下列题干,回答题:
与二分搜索算法类似,设计k分搜索算法(k>2)如下:首先检查n/k处(n为被搜索集合的元素个数)的元素是否等于要搜索的值,然后检查2n/k处的元素,…,这样,或者找到要搜索的元素,或者把集合缩小到原来的1/k;未找到要搜索的元素时,则继续在得到的集合上进行k分搜索;如此进行下去,直到找到要搜索的元素或搜索失败。此k分搜索算法在最坏情况下搜索成功的时间复杂度为( 1 ),在最好情况下搜索失败的时间复杂度为( 2 )。
请选择( 1 )处最佳答案

进入在线模考

参考答案

C

答案解析

可以构造k叉树来描述k分查找。k分查找在查找成功时进行比较的关键个数最多不超过树的深度,即[n logkn(k+1)]+1,所以k分搜索算法在最坏情况下搜索成功的时间复杂度为0(n logn)。同样道理。查找不成功时。和给定值比较的关键字个数也至多为[n logkn(k+1)]+1,所以时间复杂度为0(n logk n)。

你可能感兴趣的试题

找试题 · 找答案 · 找资料 在线模考