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

algorithm java permutation big-o

2022-09-03 03:30:42

将数组 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，我不确定什么时候考虑log函数。

答案 1

该条目将立即填充。该条目有被随机数填充的概率。因此，我们需要平均随机数来填补第二个位置。通常，对于条目，我们需要平均随机数，对于每个数字，我们需要比较以检查它是否唯一。011 - 1 / n = (n - 1) / nn / (n - 1)kn / (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))Ω(n^2*log(n))O(n^2*log(n))

Θ（n^2*log（n））

操作。

答案 2

这类似于优惠券收集器问题。你从n个项目中进行选择，直到你得到一个你还没有的项目。平均而言，您有O（n log n）次尝试（请参阅链接，分析并非微不足道）。在最坏的情况下，您每次尝试都会检查n个元素。这导致 O（N^2 log N）的平均复杂度