为什么这个算法的Big-O是N^2*log N

将数组 a 从 a[0] 填充到 a[n-1]：生成随机数，直到得到之前索引中不存在的数字。

这是我的实现：

public static int[] first(int n) {
    int[] a = new int[n];
    int count = 0;

    while (count != n) {
        boolean isSame = false;
        int rand = r.nextInt(n) + 1;

        for (int i = 0; i < n; i++) {
            if(a[i] == rand) isSame = true;
        }

        if (isSame == false){
            a[count] = rand;
            count++;
        }
    }

    return a;
}

我以为是 N^2 但显然是 N^2logN 并且我不确定何时考虑对数函数。

The 0条目立即被填写。这1进入有概率1 - 1 / n = (n - 1) / n被随机数填充。所以我们需要平均n / (n - 1)随机数填充第二个位置。一般来说，对于k我们平均需要的条目n / (n - k)随机数以及我们需要的每个数字k比较以检查它是否唯一。

所以我们需要

n * 1 / (n - 1) + n * 2 / (n - 2) + ... + n * (n - 1) / 1

平均比较。如果我们考虑总和的右半部分，我们会发现这一半大于

n * (n / 2) * (1 / (n / 2) + 1 / (n / 2 - 1) + ... + 1 / 1)

已知分数之和为Θ(log(n))因为它是一个谐波级数 http://en.wikipedia.org/wiki/Harmonic_series_%28mathematics%29。所以总和是Ω(n^2*log(n))。以类似的方式，我们可以将总和表示为O(n^2*log(n))。这意味着平均我们需要

θ(n^2*log(n))

运营。