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

Question

将数组a从[0]填充到[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,我不确定何时考虑日志功能.

Answer 1

该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))因为它是一个谐波系列.所以总和是?(n^2*log(n)).以类似的方式,我们可以显示总和O(n^2*log(n)).这意味着我们平均需要

Θ(N ^ 2*的log(n))

操作.

Answer 2

这类似于优惠券收集器问题.你从n个项目中挑选,直到你得到一个你还没有的项目.平均而言,您有O(n log n)次尝试(请参阅链接,分析并非易事).在最坏的情况下,您会检查每次尝试的n个元素.这导致平均复杂度为O(N ^ 2 log N)