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

Time Complexity Analysis of k-Bisection Search

作　　者：傅晓航 郑欢欢 FU Xiao-hang;ZHENG Huan-huan(School of Computer Science&Engineering,Nanjing University of Science&Technology,Nanjing 210094,China)

机构地区：[1]南京理工大学计算机科学与工程学院,江苏南京210094

出　　处：《计算机技术与发展》2021年第2期175-179,共5页Computer Technology and Development

基　　金：国家级大学生创新创业训练计划项目(201910288048Z)。

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

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

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]