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

Question

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

这是我的实现：

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 并且我不确定何时考虑对数函数。

Answer 1

如果我没记错的话，log N部分来自这部分：

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

请注意，我将 n 更改为 count，因为您知道在每个循环中您的数组中只有 count 个元素。

Answer 2

这与 Coupon Collector 问题类似。你从 n 件物品中挑选，直到你得到一件你还没有的物品。平均而言，您有 O(n log n) 次尝试（参见 link，分析并不简单）。在最坏的情况下，您会在每次尝试时检查 n 个元素。这导致平均复杂度为 O(N^2 log N)

Answer 3

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))，因为它是 harmonic series。所以总和是Ω(n^2*log(n))。以类似的方式，我们可以显示总和为 O(n^2*log(n))。这意味着我们平均需要

Θ(n^2*log(n))

操作。

Answer 4

您的算法不是O(n^2 lg n)，因为您的算法可能会永远循环而无法完成。想象一下，在您的第一次传递中，您获得了一些价值 $X$，并且在随后的每次传递中，试图获得第二个值，您将永远获得 $X$。毕竟，我们在这里谈论的是最坏的情况。那将永远循环。因此，由于您的最坏情况永远不会结束，因此您无法真正分析。

如果您想知道，如果您知道 n 始终是数组的大小和值的上限，您可以简单地这样做：

int[] vals = new int[n];
for(int i = 0; i < n; i++) {
    vals[i] = i;
}
// fischer yates shuffle
for(int i = n-1; i > 0; i--) {
   int idx = rand.nextInt(i + 1);
   int t = vals[idx];
   vals[idx] = vals[i];
   vals[i] = t;
}

向下一环，向后一环。 O(n)。简单。

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

Why is the Big-O of this algorithm N^2*log N

java

algorithm

big-o

permutation