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

傅晓航，郑欢欢

(南京理工大学 计算机科学与工程学院，江苏 南京 210094)

0 引 言

分治算法是一个将规模较大问题分解为多个规模相同子问题的算法[1]。许多算法都是基于分治策略实现的，例如搜索、快速排序、归并排序、TOP-K算法等等；此外分治策略能够应用于许多算法的优化，例如防火墙规则匹配算法、蚁群算法、并行碰撞检测算法等等，相关研究如文献[2-5]。分治策略的核心思想是将一个问题等分为多个形式相同的子问题，图1所示为每次将问题划分为两个相等子问题时的分治算法。为提高算法的性能，该文将研究将原问题分解为多少个子问题时分治算法的效率最高。

图1 每次划分两子问题的分治算法

该文以搜索为例，搜索是指在一个排好序的数组中寻找与给定数值x相等的元素，很容易想到的方法是将数组遍历，但是遍历的复杂度为O(n)，当数组的规模n很大时，查找次数将会很大。

二分搜索是将数组每次分为相等的两部分，将待查元素x与数组中点处的元素a[n/2]比较，若a[n/2]=x则搜索成功；若a[n/2]>x，则待查元素x在数组左半区；若a[n/2]

根据分治策略的研究可以想到，如果每次将数组分为相等的更多部分，比如三部分甚至是k部分，算法性能还会不会有所提升。每次将数组分为更多的部分，则每趟查找能够将数组缩小到更小的范围，然而每趟需要进行额外的查找，从定性分析的角度，总的查找次数增加或减少均是有可能的。随着k的增加，平均查找次数可能先减少，达到最低后再增加；也……