无序数组查找多秩目标元素的最优时间复杂度问题

问题描述 #

给定包含n个互异元素的无序数组，其中n为2的幂，需要查找的目标元素共log₂n个，对应数组升序排序后位置为1,2,4,8,16,…,n/2的元素（排序后位置1为全局最小值，位置n为全局最大值），求查找所有目标元素的最优时间复杂度。

原有推导思路 #

• 基于中位数的中位数（median of medians）算法，可以在O(n)时间复杂度下从无序数组中找到任意指定秩的元素
• 未按1、2、4、8…n/2的顺序逐个查找，而是首先选取待查找目标集合的中间秩k（对应位置为√n），以该元素为划分基准将原数组拆分为两个子数组，再分别对两个子数组递归处理剩余待查找元素
• 按该思路计算：递归共log₂log₂n层，每层总处理工作量为O(n)，因此推导总时间复杂度为O(n log log n)
• 存在疑问：对应题目给出的选项中没有该结果，推导是否存在问题

最优解法与正确结论 #

原有推导的思路不是最优方案，问题出在划分基准的选择上，最优时间复杂度实际为O(n)，推导逻辑如下：

• 观察目标位置的规律：所有待查找元素的秩最大为n/2，其余待查找元素的秩1,2,4…n/4均小于n/2
• 第一步先找秩为n/2的中位数，使用中位数的中位数算法耗时O(n)，完成划分后，所有小于该中位数的元素构成大小为n/2的左子数组，其余所有待查找目标全部落在这个左子数组中，右半部分所有元素可以直接丢弃，不需要参与后续计算
• 第二步在大小为n/2的左子数组中，找秩为n/4的元素（对应原数组秩为n/4的目标），耗时O(n/2)，划分后同样将所有小于该元素的元素构成大小为n/4的左子数组，剩余待查找目标全部在这个更小的子数组中，丢弃其余部分
• 以此类推，每一步都处理当前子数组中秩为当前子数组大小一半的目标元素，划分后仅保留左半段继续递归
• 总耗时为等比数列求和：O(n) + O(n/2) + O(n/4) + ... + O(2) = O(2n) = O(n)

注：原有思路选择待查集合的中间秩作为划分点，会导致左右两个子数组都需要递归处理，虽然每层总工作量为O(n)，但多了loglogn层递归，得到的O(n log log n)是可行解但不是最优解。

内容的提问来源于stack exchange，提问作者user3699192