java - 第 K 个最小数算法做额外的工作？

Question

所以我正在准备技术面试，我的练习题之一是第 K 个最小的数字。我知道我可以为 O(n * log(n)) 时间做一个排序并为 O(n * log(k)) 使用堆。但是我也知道我可以对它进行分区(类似于快速排序)，用于平均 O(n) 的情况。

实际计算出的平均时间复杂度应该是:

我使用 WolframAlpha 仔细检查了这个数学，它同意。

所以我编写了我的解决方案，然后我计算了随机数据集的实际平均时间复杂度。对于较小的 n 值，它非常接近。例如，当我期望 5.7 左右时，n=5 可能会给我一个 6.2 左右的实际值。这个稍微多一点的错误是一致的。

当我增加 n 的值时，情况只会变得更糟。例如，对于 n=5000，我的实际平均时间复杂度约为 15,000，而它应该略小于 10,000。

所以基本上，我的问题是这些额外的迭代从何而来？是我的代码错了，还是我的数学？我的代码如下:

import java.util.Arrays;
import java.util.Random;

public class Solution {
    static long tc = 0;
    
    static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    static int kMin(int[] arr, int k) {
        arr = arr.clone();
        int pivot = pivot(arr);
        if(pivot > k) {
            return kMin(Arrays.copyOfRange(arr, 0, pivot), k);
        } else if(pivot < k) {
            return kMin(Arrays.copyOfRange(arr, pivot + 1, arr.length), k - pivot - 1);
        }
        return arr[k];
    }

    static int pivot(int[] arr) {
        Random rand = new Random();
        int pivot = rand.nextInt(arr.length);
    
        swap(arr, pivot, arr.length - 1);
    
        int i = 0;
        for(int j = 0; j < arr.length - 1; j++) {
            tc++;
            if(arr[j] < arr[arr.length - 1]) {
                swap(arr, i, j);
                i++;
            }
        }
        swap(arr, i, arr.length - 1);
        return i;
    }

    public static void main(String args[]) {
        int iterations = 10000;
        int n = 5000;
        for(int j = 0; j < iterations; j++) {
            Random rd = new Random(); 
            int[] arr = new int[n];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = rd.nextInt();
            }
            int k = rd.nextInt(arr.length - 1);
            kMin(arr, k);
        }
        System.out.println("Actual: " + tc / (double)iterations);
        
        double expected = 2.0 * n - 2.0 - (Math.log(n) / Math.log(2));
        System.out.println("Expected: " + expected);
    }
    

}

Answer 1

正如您和其他人在评论中指出的那样，您的计算假设数组在每次迭代中被随机主元分成两半，这是不正确的。这种不均匀的拆分会产生重大影响:例如，当您尝试选择的元素是实际中值时，在一个随机主元选择之后数组的预期大小是原始值的 75%，因为您总是会选择两个数组中较大的一个。

为了准确估计每个 n 和 k 值的预期比较，David Eppstein 发布了一个易于理解的分析 here并推导出这个公式:

这是对您的值的非常接近的估计，即使这假定数组中没有重复项也是如此。

Calculating从 1 到 n-1 的 k 的预期比较次数，正如您所做的那样，给出 ~7.499 * 10^7 n=5000 时的总比较，或者几乎恰好 15,000 每次 Quickselect 调用的比较如您观察到的那样。