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

摘要

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