查找多个元素时线性搜索的时间复杂度疑问及基准分析

问题背景 #

对比暴力搜索与自定义搜索方法时，需估算暴力搜索的复杂度：检查指定元素是否存在于无序列表中，以包含[1..99999]的整数列表为测试样本（共99999个元素），通过线性遍历统计找到所有目标元素所需的比较次数（对应代码中search.contains(values.get(i))操作）。

基准测试结果（1000次运行） #

• 搜索1个元素：平均约50000次比较，对应期望公式$\frac{N+1}{2}$，复杂度$O(N)$，此情况已理解；
• 搜索2个元素：平均约65000次比较，需推导对应的数学公式与计算复杂度；
• 搜索3个元素：平均约75000次比较，需推导对应的数学公式与计算复杂度。

测试代码 #

public static void main(String[] args) {
    List<Integer> values = IntStream.range(1, 100_000).boxed().toList();

    List<Integer> results1 = new ArrayList<>();
    List<Integer> results2 = new ArrayList<>();
    List<Integer> results3 = new ArrayList<>();

    Set<Integer> search1 = Set.of(1);
    Set<Integer> search2 = Set.of(1, 2);
    Set<Integer> search3 = Set.of(1, 2, 3);

    for (int i = 0; i < 1000; i++) {
        results1.add(search(values, search1));
        results2.add(search(values, search2));
        results3.add(search(values, search3));
    }
    System.out.println("Search 1: " + results1.stream().mapToInt(i->i).average().getAsDouble());
    System.out.println("Search 2: " + results2.stream().mapToInt(i->i).average().getAsDouble());
    System.out.println("Search 3: " + results3.stream().mapToInt(i->i).average().getAsDouble());
}

private static int search(List<Integer> list, Set<Integer> search) {
    List<Integer> values = new ArrayList<>(list);
    Collections.shuffle(values);

    int i = 0;
    int found = 0;
    for (; i < values.size(); i++) {
        if (search.contains(values.get(i))) {
            ++found;
        }
        if (found == search.size()) {
            break;
        }
    }
    return i+1;
}

数学公式推导与复杂度分析 #

核心结论 #

对于包含$N$个元素的无序列表，查找$k$个不同目标元素时，找到所有目标所需的平均比较次数的数学公式为：
$$E(k) = \frac{k \times (N+1)}{k+1}$$

推导依据 #

问题本质是：在随机打乱的数组中，找到第$k$个目标元素时的遍历次数（1-based位置）的期望值。利用排列的对称性可知，$k$个目标元素在数组中的位置的期望是均匀分布的——将整个数组的位置划分为$k+1$个等期望长度的区间，因此第$m$个目标元素的期望位置为$\frac{m \times (N+1)}{k+1}$。当找到第$k$个目标元素时停止遍历，此时的平均比较次数就是第$k$个目标元素的期望位置。

验证与结果 #

• 当$k=1$，$N=99999$时：$E(1)=\frac{1 \times (99999+1)}{1+1}=50000$，与测试结果完全吻合；
• 当$k=2$，$N=99999$时：$E(2)=\frac{2 \times (99999+1)}{2+1}≈66666.67$，与测试结果的65000接近，差异源于测试样本的随机误差；
• 当$k=3$，$N=99999$时：$E(3)=\frac{3 \times (99999+1)}{3+1}=75000$，与测试结果完全吻合。

时间复杂度 #

从公式可以看出，平均比较次数的主导项为$\frac{k}{k+1}N$，当$k$远小于$N$时，$\frac{k}{k+1}$趋近于1，因此时间复杂度仍为**$O(N)$**——即使查找多个目标元素，暴力遍历的渐近复杂度依然是线性的，只是常数因子随$k$增大而趋近于1。

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