k 分搜索的时间复杂度分析-《计算机技术与发展》

文章信息/Info

Author(s):: FU Xiao-hang; ZHENG Huan-huan; School of Computer Science & Engineering,Nanjing University of Science & Technology,Nanjing 210094,China

Keywords:: divide-and-conquer; binary search; k -bisection search; optimal algorithm; inductive method

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

Abstract:: The idea of a divide-and-conquer strategy is to solve a large problem by breaking it down into subproblems of the same form. Search refers to finding the elements equal to the given value x in an ordered array. The traditional search algorithm is traversal, while the binary search is a search algorithm based on divide-and-conquer strategy. The binary search is to divide the array into? two equal parts each time,compare the elements to be searched with the elements in the middle of the array,if equal,the search is successful; otherwise, the search scope will be reduced to half of the original,and so on,until the elements to be checked are found. Compared with traversal, the complexity of binary search is significantly reduced. On the basis of binary search,the array can be divided into more parts each time, that is, k -bisection search. The time complexity of k -bisection search algorithm is the lowest when searching for the value of k ,which can further optimize the search algorithm. Through analysis,induction and proof,the time complexity of k -score search is O(k log_kn) . Because the function is increasing,the binary search is the most efficient search algorithm,of which the complexity is O( log₂ n) . In addition,when k = n , k-bisection search degenerates to ergodic,and the complexity degenerates to O(n) .