k 分搜索的时间复杂度分析

来源：计算机技术与发展杂志2021年第02期北京时间：

作者：傅晓航;郑欢欢

摘要：分治策略的思想是将一个规模较大的问题分解为多个形式相同的子问题来解决。搜索是指在一个排好序的数组中寻找与给定数值 x 相等的元素, 传统的搜索算法是遍历, 而二分搜索是一种基于分治策略的搜索算法。 二分搜索是将数 组每次分为相等的两部分,将待查元素 x 与数组中间的元素比较,若相等则搜索成功;否则将搜索范围缩小为原来的一半, 之后以此类推,直到找到待查元素,与遍历相比,二分搜索复杂度明显降低。 以二分搜索为基础,每次可以将数组分为更 多部分,即 k 分搜索,探寻 k 为何值时 k 分搜索算法的时间复杂度最低,能够对搜索算法进一步优化。 通过分析、归纳与证 明,得出 k 分搜索的时间复杂度为 O(k logkn) ,由于该函数是递增的,因此二分搜索是效率最高的搜索算法,复杂度为 O(log2 n) ;此外,当 k = n 时, k 分搜索退化为遍历,复杂度退化为 O(n) 。

关键词：分治算法;二分搜索; k 分搜索;最优算法;归纳法