A.O(logn)B.O(nlogn)C.O(logkn)D.O(nlogkn)

Question

A．O(logn)

B．O(nlogn)

C．O(logkn)

D．O(nlogkn)

Answer 1

正确答案：C
解析：与二分查找法类似，k分查找法可用k叉树来描述。k分查找法在查找成功时进行比较的关键字个数最多不超过树的深度，而具有n个节点的k叉树的深度为[logkn(k+1)]+1，所以k分查找法在查找成功时和给定值进行比较的关键字个数至多为[logkn)+1，即时间复杂度为O(logkn)。同时，k分查找法在查找不成功时，和给定值进行比较的关键字个数也至多为[logkn(k+1)]+1，即时间复杂度为O(logkn)。